Максимальный XOR (Hard)
Максимальный XOR (Hard)
У Васи есть N целых неотрицательных чисел a_1, a_2, ..., a_N. Так как ему и его другу Виталию уже изрядно надоели банальные битовые операции AND и OR, они решили приняться за что-то иное: Вася попросил программиста Виталия перебрать на компьютере все возможные непустые подпоследовательности исходной последовательности из N чисел, и вычислить XOR-сумму каждой из них. Среди полученных 2^N-1 чисел ребята выбрали максимальное.
Но так как в этой задачі в отличие от предыдущей у Васи стало значительно больше чисел, то посчитать ответ на эту задачу "в лоб" Виталий никак не сможет. Вам нужно помочь ему в этом, иначе математик Васиий вообще разочаруется в программистах.
Входные данные
В первой строке задано число N, 1 ≤ N ≤ 100000. В следующей строке задано N чисел, 0 ≤ a_i ≤ 2·10^9.
Выходные данные
Выведите единственное число - ответ на задачу.
Пример
5 1 2 3 4 5
7