СуперБик#11181

СуперБик

1 секунда

128 мегабайтів

Легка

Беssі та її друзі грають у копитобол на щорічному чемпіонаті Superbull, а фермер Джон відповідає за те, щоб зробити турнір якомога захопливішим. У Superbull бере участь $n$ команд. Кожній команді присвоюється унікальний цілочисельний ідентифікатор у діапазоні від $1$ до $2^{30} - 1$ 2^{30} - 1, щоб відрізняти її від інших команд.

Superbull — це турнір на вибування. Після кожної гри фермер Джон вибирає, яку з двох команд виключити з турніру, і виключена команда більше не може брати участь у подальших іграх. Турнір закінчується, коли залишається лише одна команда.

Фермер Джон помічає досить незвичну властивість результатів цих матчів. У кожній грі загальна кількість очок, набраних двома командами, дорівнює побітовій операції виключного АБО (XOR) над ідентифікаторами цих команд. Наприклад, якщо команди $12$ та $20$ грають одна проти одної, у грі буде набрано $24$ очки, оскільки $01100 XOR 10100 = 11000$ 01100 \mathbin{\text{ XOR }} 10100 = 11000.

Фермер Джон вважає, що чим більше очок набрано у грі, тим цікавішою вона стає. Тому він хоче вибрати таку послідовність ігор, щоб загальна кількість набраних очок за весь турнір була якомога більшою. Допоможіть фермеру Джону організувати матчі.

Вхідні дані

У першому рядку міститься одне ціле число $n (1 \leq n \leq 2000)$ n~(1 \le n \le 2000). У наступних $n$ рядках міститься по одному ідентифікатору команди.

Вихідні дані

Виведіть максимально можливу загальну кількість очок, яку можна набрати в турнірі Superbull.

Приклади

Один зі способів набрати в цілому $37$ очок виглядає так. Спочатку ФД зводить команди $3$ та $9$ і вирішує, що команда $9$ перемагає, після чого в турнірі залишаються команди $6$ , $9$ та $10$ . Потім він зводить команди $6$ та $9$ і дозволяє команді $6$ перемогти. Тепер у турнірі залишаються команди $6$ та $10$ . Нарешті, команди $6$ та $10$ зустрічаються одна з одною, і перемагає команда $10$ .

Загальна кількість набраних очок дорівнює

(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

Приклад 1

Примітка

Побітова операція виключного АБО (XOR), яку зазвичай позначають символом $\oplus$ , — це побітова операція, яка застосовує логічну операцію виключного АБО до кожної відповідної пари бітів двох двійкових чисел. Результат у кожній позиції дорівнює $1$ , якщо рівно один із двох бітів дорівнює $1$ , і $0$ , якщо обидва біти дорівнюють $0$ або обидва дорівнюють $1$ .

Наприклад,

$10100$ (десяткове $20$ ) $\oplus$ $01100$ (десяткове $12$ ) $=$ $11000$ (десяткове $24$ ).