Джонатан сражается с приспешниками-вампирами DIO. Всего их \(n\), а их силы равны \(a_1, a_2, \dots, a_n\). \(\def\and {{\,\texttt{&}\,}}\)
Обозначим \((l, r)\) как группу, состоящую из вампиров с индексами от \(l\) до \(r\). Джонатан понимает, что сила любой такой группы находится в её самом слабом звене, то есть побитовом И. Более формально, уровень силы группы \((l, r)\) определяется как \(\)f(l,r) = a_l \and a_{l+1} \and a_{l+2} \and \ldots \and a_r.\(\) Здесь \(\and\) обозначает операцию побитового И.
Поскольку Джонатан хочет быстро победить вампиров, он разделит вампиров на подряд идущие группы так, чтобы каждый вампир был в ровно одной группе, а сумма сил групп была минимальна. Среди всех подходящих способов разделить вампиров, он хотел бы найти способ с максимальным количеством групп.
Учитывая силы каждого из \(n\) вампиров, найдите максимальное число групп среди всех возможных способов разделить вампиров с наименьшей суммой сил.
Выходные данные
Для каждого набора входных данных выведите одно целое число — максимальное количество групп среди всех возможных способов разделения вампиров с наименьшей суммой сил.
Примечание
В первом наборе входных данных оптимальным является принятие всех \(n\) вампиров за одну группу. Тогда, \(f(1,3) = 1 \and 2 \and 3 = 0\).
Во втором наборе входных данных оптимальным является создание \(2\) групп, \((2,3,1)\) и \((5,2)\). Тогда, \(f(1,3) + f(4,5) = (2 \and 3 \and 1) + (5 \and 2) = 0 + 0 = 0\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3
1 2 3
5
2 3 1 5 2
4
5 7 12 6
|
1
2
1
|