考虑g(x)操作为:从低位到高位找到第一个连续1段,然后最高位那个1往左移动一位,其余的1移动至最低位即可。
例如:312 = 100111000
g(312) = 10100011
特别的,g(1) = 2 (10), 这种二进制需要进位的情况,我们在操作二进制字符串之前需要对最高位补全一个前导零。
定义f(x)为x在二进制表示下的1个数,例如f(7)=3,f(8)=1,f(9)=2。
定义g(x)为第一个比x大的数字y,使得f(x)=f(y),例如g(1)=2,g(2)=4,g(3)=5。
小红首页有n篇笔记,第i篇笔记的点赞数量为ai,我们希望从中挑选出一些笔记,构造一个长度为m的精选队列b1,b2,......,bm。在这里,精选队列满足:对于所有的j∈[2,m],都有bj=g(bj−1)。
第一行输入一个整数n(1≤n≤105)。
第二行输入n个整数a1(1≤a1,a2,......,an≤109)。
在一行上输出一个整数, 代表最长的精选队列的长度。
输入
5
1 4 2 5 3
输出
3
说明
可以构成几种精选队列,分别为:
[1,2,4],[2,4],[3,5],[1],[2],[3],[4],[5]其中最长的为[1,2,4],长度为3