Последовательность чисел \(b_1, b_2, \ldots, b_n\) является хорошей, если \(\operatorname{mex}(b_1, b_2, \ldots, b_n) - (b_1 | b_2 | \ldots | b_n) = 1\). Здесь \(\operatorname{mex(c)}\) обозначает MEX\(^{\text{∗}}\) набора чисел \(c\), а \(|\) обозначает операцию побитового ИЛИ.
У Шохага есть целочисленная последовательность \(a_1, a_2, \ldots, a_n\). Он выполнит следующие \(q\) обновлений последовательности \(a\):
- \(i\) \(x\) — увеличить \(a_i\) на \(x\).
После каждого обновления помогите Шохагу найти длину самого длинного хорошего подмассива\(^{\text{†}}\) массива \(a\).
Выходные данные
Для каждого набора входных данных выведите \(q\) строк — в \(i\)-й строке выведите длину самого длинного хорошего подмассива \(a\) после \(i\)-го обновления.
Примечание
В первом наборе входных данных после первого обновления массив становится \([0, 0, 1, 0, 1, 1]\). Весь массив является хорошим, так как \(\operatorname{mex}([0, 0, 1, 0, 1, 1]) - (0 | 0 | 1 | 0 | 1 | 1) = 2 - 1 = 1\).
После второго обновления массив становится равен \([0, 0, 3, 0, 1, 1]\), и его подмассив \([0, 1, 1]\) имеет максимальную длину среди всех хороших подмассивов.
Наконец, после третьего обновления массив становится равен \([0, 0, 3, 0, 1, 4]\), и два его подмассива \([0, 0]\) и \([0, 1]\) имеют максимальную длину среди всех хороших подмассивов.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
6 3
0 0 1 0 1 0
6 1
3 2
6 3
3 1
1 3 1
1 1
|
6
3
2
0
|