Сегодня Кот и Лиса нашли массив \(a\), состоящий из \(n\) целых неотрицательных чисел.
Определим одиночество массива \(a\) как наименьшее целое положительное число \(k\) (\(1 \le k \le n\)) такое, что для любых двух целых положительных чисел \(i\) и \(j\) (\(1 \leq i, j \leq n - k +1\)) выполняется \(\)a_i | a_{i+1} | \ldots | a_{i+k-1} = a_j | a_{j+1} | \ldots | a_{j+k-1},\(\) где \(x | y\) обозначает операцию побитового ИЛИ чисел \(x\) и \(y\). Другими словами, побитовое ИЛИ любых \(k\) подряд идущих элементов совпадает. Заметьте, что одиночество массива \(a\) определено корректно, так как при \(k = n\) условие выполняется.
Кот и Лиса хотят узнать, насколько одинок массив \(a\). Помогите им вычислить одиночество найденного массива.
Выходные данные
Для каждого набора входных данных выведите одно целое число — одиночество данного массива.
Примечание
В первом примере одиночество массива с одним элементом равно \(1\), поэтому ответом будет \(1\).
Во втором примере побитовое ИЛИ каждого подмассива длины \(k = 1\) равняется \(2\), поэтому одиночество всего массива равно \(1\).
В седьмом примере верно, что \((0 | 1 | 3) = (1 | 3 | 2) = (3 | 2 | 2) = (2 | 2 | 1) = (2 | 1 | 0) = (1 | 0 | 3) = 3\), поэтому условие выполняется для \(k = 3\). Можно убедиться, что условие не выполняется при любом меньшем \(k\), поэтому ответ действительно равен \(3\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
1
0
3
2 2 2
3
1 0 2
5
3 0 1 4 2
5
2 0 4 0 2
7
0 0 0 0 1 2 4
8
0 1 3 2 2 1 0 3
|
1
1
3
4
4
7
3
|