给定一个长度为 $n$ 的递增整数序列 $A = a_1, a_2, \dots, a_n$，其中所有元素互不相同。我们通过以下算法生成另一个序列 $B$。

算法 1 序列生成算法
1: function GENERATE(A)
2: B ← A
3: while true do
4: B' ← B
5: Let S be the sequence by sorting B in increasing order
6: for i in [1, length of S) do
7: if si + 1 != si+1 then ▷ si is the i-th element in S
8: Add floor((si+si+1)/2) to the end of B' ▷ floor(x) is the largest integer not larger than x
9: if B = B' then
10: break
11: B ← B'
12: return B

可以证明该算法一定会终止，且 $B$ 中的元素互不相同。请计算 $B$ 的最长上升子序列的长度。

输入格式

每个测试文件中仅包含一组测试数据。 第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示序列 $A$ 的长度。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_1 < a_2 < \dots < a_n \le 10^{18}$)，表示给定的序列。

输出格式

输出一行，包含一个整数，表示 $B$ 的最长上升子序列的长度。

样例

输入 1

3
1 5 20

输出 1

11

说明

对于样例，生成的序列 $B = \{1, 5, 20, 3, 12, 2, 4, 8, 16, 6, 10, 14, 18, 7, 9, 11, 13, 15, 17, 19\}$。其最长上升子序列为 $\{1, 3, 4, 6, 7, 9, 11, 13, 15, 17, 19\}$，长度为 11。