Владик очень часто ездит на поездах. Некоторые из этих поездок запоминаются ему особо хорошо, одна из таких поездок:
Владик находится на начальной станции поезда, и сейчас в него хотят зайти n человек (включая Владика). Они уже выстроились в некотором порядке, и для каждого из них известен код города ai, в который они направляются.
Начальник поезда выбирает некоторое количество непересекающихся отрезков исходной последовательности людей (отрезки не обязаны покрывать всю последовательность). Люди, находящиеся в одном и том же отрезке, будут находиться в одном и том же вагоне поезда. Отрезки выбираются так, что если в город x едет как минимум один человек, то все люди, которые направляются в город x должны будут находиться в одном вагоне. Это обозначает, что они не имеют права принадлежать разным отрезкам. Следует заметить, что все люди, которые едут в город x, либо едут в него и находятся в одном вагоне, либо вовсе не едут никуда.
Комфортность поездки в поезде с людьми на отрезке с l по r равна XOR-у различных кодов городов у людей на отрезке с l по r. Операция XOR также известна как исключающее побитовое ИЛИ.
Общая комфортность выбранных отрезков вычисляется как сумма комфортности каждого отдельного отрезка.
Помогите Владику узнать максимальную достижимую общую комфортность.
Примечание
В первом примере выгодное разделение следующие: [4, 4] [2, 5, 2] [3], ответ считается следующим образом: 4 + (2 xor 5) + 3 = 4 + 7 + 3 = 14
Во втором примере выгодное разделение следующие: 5 1 [3] 1 5 [2, 4, 2] 5, ответ считается следующим образом: 3 + (2 xor 4) = 3 + 6 = 9.