Вам дан массив целых чисел \(a\) размера \(n\). Вы можете выбрать некое множество непересекающихся подотрезков данного массива (заметим, что некоторые элементы могут не попасть ни в один из отрезков, это не запрещено), для каждого выбранного подотрезка посчитать MEX его элементов, а затем посчитать побитовое исключающее ИЛИ (XOR) всех полученных значений MEX. Какое наибольшее значение XOR может получиться?
MEX (minimum excluded, минимальное отсутствующее) массива — это наименьшее целое неотрицательное целое число, которое не принадлежит массиву. Например:
- MEX массива \([2,2,1]\) равен \(0\), потому что \(0\) не принадлежит массиву.
- MEX массива \([3,1,0,1]\) равен \(2\), потому что \(0\) и \(1\) принадлежат массиву, а \(2\) — нет.
- MEX массива \([0,3,1,2]\) равен \(4\), потому что \(0\), \(1\), \(2\) и \(3\) принадлежат массиву, а \(4\) — нет.
Примечание
В первом наборе входных данных максимальный XOR равен \(2\), если взять весь массив, \(\operatorname{MEX}([1, 0]) = 2\).
Во втором наборе входных данных максимальный XOR равен \(6\), если выделить отрезки \([1, 2, 0]\) и \([7, 1, 2, 0, 2, 4, 3]\):
- \(\operatorname{MEX}([1, 2, 0]) = 3\),
- \(\operatorname{MEX}([7, 1, 2, 0, 2, 4, 3]) = 5\),
таким образом, побитовое исключающее ИЛИ равно
\(5 \oplus 3=6\).
В третьем наборе входных данных максимальный XOR равен \(7\), если выделить отрезки \([1, 0]\) и \([7, 1, 2, 0, 2, 4, 3]\):
- \(\operatorname{MEX}([1, 0]) = 2\),
- \(\operatorname{MEX}([7, 1, 2, 0, 2, 4, 3]) = 5\),
таким образом, побитовое исключающее ИЛИ равно
\(5 \oplus 2 = 7\).