Superbull#11181

Superbull

1 secondo

128 megabyte

Facile

Bessie e i suoi amici giocano a calcio-zoccolo nel campionato annuale Superbull, e il fattore John è responsabile di rendere il torneo il più emozionante possibile. Al Superbull partecipano $n$ squadre. A ogni squadra viene assegnato un identificatore intero unico nell'intervallo da $1$ a $2^{30} - 1$ 2^{30} - 1, per distinguerla dalle altre squadre.

Superbull è un torneo a eliminazione diretta. Dopo ogni partita, il fattore John scieglie quale delle due squadre eliminare dal torneo, e la squadra eliminata non può più partecipare alle partite successive. Il torneo termina quando resta solo una squadra.

Il fattore John nota una proprietà piuttosto insolita dei risultati di queste partite. In ogni partita, il numero totale di punti segnati dalle due squadre è uguale all'operazione bit a bit di OR esclusivo (XOR) applicata agli identificatori di quelle squadre. Ad esempio, se le squadre $12$ e $20$ giocano l'una contro l'altra, nella partita verranno segnati $24$ punti, poiché $01100 XOR 10100 = 11000$ 01100 \mathbin{\text{ XOR }} 10100 = 11000.

Il fattore John ritiene che quanti più punti vengono segnati in una partita, tanto più interessante essa diventi. Perciò vuole scegliere una sequenza di partite tale che il numero totale di punti segnati durante tutto il torneo sia il più grande possibile. Aiuta il fattore John a organizzare le partite.

Input

La prima riga contiene un singolo numero intero $n (1 \leq n \leq 2000)$ n~(1 \le n \le 2000). Le successive $n$ righe contengono ciascuna un identificatore di squadra.

Output

Stampa il numero massimo possibile di punti totali che si possono segnare nel torneo Superbull.

Esempi

Uno dei modi per ottenere un totale di $37$ punti è il seguente. Per prima cosa, FJ fa scontrare le squadre $3$ e $9$ e decide che la squadra $9$ vince, dopo di che nel torneo restano le squadre $6$ , $9$ e $10$ . Poi fa scontrare le squadre $6$ e $9$ e lascia vincere la squadra $6$ . Ora nel torneo restano le squadre $6$ e $10$ . Infine, le squadre $6$ e $10$ si affrontano, e vince la squadra $10$ .

Il numero totale di punti segnati è pari a

(3 XOR 9) + (6 XOR 9) + (6 XOR 10) = 10 + 15 + 12 = 37

(3 \mathbin{\text{ XOR }} 9) + (6 \mathbin{\text{ XOR }} 9) + (6 \mathbin{\text{ XOR }} 10) = 10 + 15 + 12 = 37

Esempio 1

Nota

L'operazione bit a bit di OR esclusivo (XOR), solitamente indicata con il simbolo $\oplus$ , è un'operazione bit a bit che applica l'operazione logica di OR esclusivo a ogni coppia corrispondente di bit di due numeri binari. Il risultato in ogni posizione è $1$ se esattamente uno dei due bit è $1$ , e $0$ se entrambi i bit sono $0$ oppure entrambi sono $1$ .

Ad esempio,

$10100$ (decimale $20$ ) $\oplus$ $01100$ (decimale $12$ ) $=$ $11000$ (decimale $24$ ).