Problem description


(Nie)uczciwy remik
(H)
Limit pamięci: 256 MB
Limit czasu: 1.00 s

Rodzina Jasia często spędza wakacyjne wieczory grając w remika – karcianą grę strategiczno-losową. Jaś uważa ją za bardziej strategiczną lub losową w zależności od tego, jak mu poszło w danym rozdaniu.

Każdy gracz zaczyna z taką samą liczbą kart. Następnie, podczas kolejnych rund gracze wykładają swoje karty na stół zgodnie z zasadami, które nie są istotne dla tego zadania. Zwycięzcą zostaje gracz, który jako pierwszy pozbędzie się wszystkich swoich kart. Każdy z pozostałych graczy oblicza sumę wartości kart, które mu pozostały, i odejmuje ją od swojego wyniku. Wynik zwycięzcy jest natomiast powiększany o sumę tych wartości.

Rodzina Jasia używa do gry nietypowych kart – na każdej z nich znajduje się liczba od 0 do 260 − 1. Wszystkie karty mają taki sam kolor, a liczby na różnych kartach mogą powtarzać się dowolnie wiele razy.

Niestety, tym razem losowy aspekt gry doprowadził do sromotnej porażki Jasia – po raz piąty tego wieczoru wygrał wuj Janusz. Jaś, któremu pozostało N kart na ręce, postanowił uciec się do podstępu, aby zminimalizować swoje straty. Potrafi on niepostrzeżenie zmienić dwie sąsiednie karty z liczbami x oraz y w jedną kartę z liczbą x ⊕ y (xor x oraz y) . Tę operację Jaś może wykonać dowolnie wiele razy, jednak nie chce on zamieniać miejscami kart na ręce – to byłby już zbyt zuchwały przekręt.

Jaka jest minimalna liczba punktów, którą Jaś może stracić, jeśli będzie oszukiwał w optymalny sposób?

Wejście

W pierwszym wierszu wejścia znajduje się liczba N – liczba kart na ręce Jasia. Drugi wiersz zawiera N liczb całkowitych pooddzielanych pojedynczymi odstępami – opis kart na ręce Jasia w kolejności od lewej do prawej.

Wyjście

W jedynym wierszu wyjścia należy wypisać jedną liczbę naturalną – minimalną możliwą sumę liczb napisanych na kartach z ręki Jasia po wykonaniu optymalnego ciągu operacji łączenia w pary sąsiednich kart.

Ograniczenia

1 ≤ N ≤ 100 000, każda karta ma wartość z przedziału [0,260−1].

Przykłady

Wejście Wyjście Wyjaśnienie
4
5 4 2 4
7

Optymalny wynik to 7. Jaś może go uzyskać na przykład łącząc pierwsze dwie karty: 5 ⊕ 4 = 1, co daje sumaryczną wartość 1 + 2 + 4.

Wejście Wyjście
3
42 42 0
0