Макс находится на начальной станции поезда, и сейчас в него хотят зайти n человек (включая саму Макс). Они уже выстроились в некотором порядке, и для каждого из них известен код города a
i, в который они направляются.
Начальник поезда выбирает некоторое количество непересекающихся отрезков исходной последовательности людей (отрезки не обязаны покрывать всю последовательность). Люди, находящиеся в одном и том же отрезке, будут находиться в одном и том же вагоне поезда. Отрезки выбираются так, что если в город X едет как минимум один человек, то все люди, которые направляются в город X должны будут находиться в одном вагоне. Это обозначает, что они не имеют права принадлежать разным отрезкам. Следует заметить, что все люди, которые едут в город X, либо едут в него и находятся в одном вагоне, либо вовсе не едут никуда.
Комфортность поездки в поезде с людьми на отрезке с l по r равна XOR-у различных кодов городов у людей на отрезке с l по r. Операция XOR также известна как исключающее побитовое ИЛИ.
Общая комфортность выбранных отрезков вычисляется как сумма комфортности каждого отдельного отрезка.
Помогите Макс узнать максимальную достижимую общую комфортность.
Входные данные:
Первая строка содержит натуральное число n - число людей (1 <= n <= 5000).
Вторая строка содержит n целых чисел a
i (0 <= a
i <= 5000) - код города, в который направляется i-й человек.
Выходные данные:
Выведите одно целое число - максимальную общую комфортность.
Примеры:
| Входные данные |
Выходные данные |
6
4 4 2 5 2 3 |
14 |
9
5 1 3 1 5 2 4 2 5 |
9 |