Question
Balance Blend
Bob has an array B of M integers. An array is deemed crowded if there exists an index j (1 ≤ j ≤ M-1) where max(Bj, Bj+1) > 2 x min(Bj, Bj+1). Find the minimum number of elements to insert at any positions to ensure the array is not crowded.
Input
The first line of the input contains a single integer M.
The second line of the input contains M space-separated integers.
Constraints
2 ≤ M ≤ 105
1 ≤ Bi ≤ 109
The second line of the input contains M space-separated integers.
Constraints
2 ≤ M ≤ 105
1 ≤ Bi ≤ 109
Output
Print the minimum number of elements which need to be added at any positions so that the given array is not populated.
Example
Sample Input
2
6 1
Sample Output
2
Explanation
You can insert two elements 4 and 2. The array becomes [6, 4, 2, 1]. Now, the array is not populated.
2
6 1
Sample Output
2
Explanation
You can insert two elements 4 and 2. The array becomes [6, 4, 2, 1]. Now, the array is not populated.