codeforces825C-Multi-judge Solving

C. Multi-judge Solving time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output

Makes solves problems on Decoforces and lots of other different online judges. Each problem is denoted by its difficulty — a positive integer number. Difficulties are measured the same across all the judges (the problem with difficulty d on Decoforces is as hard as the problem with difficulty d on any other judge).

Makes has chosen n problems to solve on Decoforces with difficulties a1, a2, ..., an. He can solve these problems in arbitrary order. Though he can solve problem i with difficulty ai only if he had already solved some problem with difficulty  (no matter on what online judge was it).

Before starting this chosen list of problems, Makes has already solved problems with maximum difficulty k.

With given conditions it's easy to see that Makes sometimes can't solve all the chosen problems, no matter what order he chooses. So he wants to solve some problems on other judges to finish solving problems from his list.

For every positive integer y there exist some problem with difficulty y on at least one judge besides Decoforces.

Makes can solve problems on any judge at any time, it isn't necessary to do problems from the chosen list one right after another.

Makes doesn't have too much free time, so he asked you to calculate the minimum number of problems he should solve on other judges in order to solve all the chosen problems from Decoforces.

Input

The first line contains two integer numbers n, k (1 ≤ n ≤ 103, 1 ≤ k ≤ 109).

The second line contains n space-separated integer numbers a1, a2, ..., an (1 ≤ ai ≤ 109).

Output

Print minimum number of problems Makes should solve on other judges in order to solve all chosen problems on Decoforces.

Examples input 3 3 2 1 9 output 1 input 4 20 10 3 6 3 output 0 Note

In the first example Makes at first solves problems 1 and 2. Then in order to solve the problem with difficulty 9, he should solve problem with difficulty no less than 5. The only available are difficulties 5 and 6 on some other judge. Solving any of these will give Makes opportunity to solve problem 3.

In the second example he can solve every problem right from the start.

题目大意： 给你题目数量和每一道题的题目难度，然后再给你你已经解决的最大问题难度，询问如果要解决所有问题，需要解决的最小问题数量。 解题思路 ：这道题，我们需要关注的一个重点在 ，如果题目难度大于我们能解决问题难度的两倍，则我们需要再解决一道两倍问题难度的题，才能够解决这道问题。直到所有的问题都小于最大能解决问题的难度的两倍，即能够被解决，否则还是需要我们再解决问题。另外需要注意的是，如果能解决问题，则当前能解决的问题的最大难度需要更新，所以我们需要对题目难度排序后再进行处理。 ac代码： #include <cstdio> #include <algorithm> #include <iostream> using namespace std; int a[1005]; int main() { int n, k, sum, i; while(~scanf("%d%d", &n, &k)) { sum = 0; for(i=0;i<n;i++) scanf("%d", &a[i]); sort(a,a+n); for(i=0;i<n;i++) { while(a[i]>2*k) { sum++; k*=2; } k=max(k, a[i]); } printf("%d\n", sum); } return 0; } 题目链接： 点击打开链接http://codeforces.com/problemset