У YouKn0wWho есть последовательность целых чисел \(a_1, a_2, \ldots a_n\). Он собирается разбить последовательность \(a\) на один или несколько последовательных подмассивов так, чтобы каждый элемент \(a\) принадлежал ровно одному подмассиву. Пусть \(k\) — количество получившихся подмассивов, а \(h_1, h_2, \ldots, h_k\) — длины самых наибольших возрастающих подпоследовательностей соответствующих подмассивов.
Например, если разделить \([2, 5, 3, 1, 4, 3, 2, 2, 5, 1]\) на \([2, 5, 3, 1, 4]\), \([3, 2, 2, 5]\), \([1]\), то \(h = [3, 2, 1]\).
YouKn0wWho интересуется, можно ли разделить последовательность \(a\) так, чтобы побитовое исключающее ИЛИ чисел \(h_1, h_2, \ldots, h_k\) было равно \(0\). Вы должны сказать, возможно ли это.
Наибольшая возрастающая подпоследовательность (НВП, LIS) последовательности \(b_1, b_2, \ldots, b_m\) — это самая длинная последовательность индексов \(i_1, i_2, \ldots, i_k\) таких, что \(i_1 \lt i_2 \lt \ldots \lt i_k\) и \(b_{i_1} \lt b_{i_2} \lt \ldots \lt b_{i_k}\). Например, НВП массива \([2, 5, 3, 3, 5]\) — это \([2, 3, 5]\), которая имеет длину \(3\).
Массив \(c\) является подмассивом массива \(b\), если \(c\) может быть получен из \(b\) удалением нескольких (возможно, ни одного или всех) элементов из начала и нескольких (возможно, ни одного или всех) элементов из конца.
Примечание
В первом наборе входных данных YouKn0wWho может разделить последовательность следующим образом: \([1, 3, 4]\), \([2, 2]\), \([1, 5]\). Таким образом, длины НВП будут \(h = [3, 1, 2]\), а побитовое исключающее ИЛИ длин НВП будет \(3 \oplus 1 \oplus 2 = 0\).
Во втором наборе входных данных можно показать, что невозможно разбить последовательность на подмассивы, удовлетворяющие условию.