Description

给你一个长度为n的递增序列ai。

若一个序列c所有i都满足c[i] < c[i+1] <= c[i]*2，则称c序列为zq序列。

设b是a的一个子序列，请你求出当b序列是一个zq序列时，长度最大可能是多少。

Input

第一行为数组长度n。

第二行n个整数分别代表a_i。(1 <= n <= 200,000 , 1 <= a[i] <= 1,000,000,000)

Output

当b序列是一个zq序列时，长度最大可能是多少。

Samples

10
1 2 5 6 7 10 21 23 24 49

4

5
2 10 50 110 250

1

6
4 7 12 100 150 199

3

Note

样例一: b = [5,6,7,10] 样例三: b = [4,7,12] 或 [100,150,199]