SuperBuğa#11181

SuperBuğa

1 saniyə

128 meqabayt

Asan

Bessie və dostları illik Superbull çempionatında dırnaqbol oynayırlar, Fermer Con isə turniri mümkün qədər maraqlı etməkdən məsuldur. Superbull-da $n$ komanda iştirak edir. Hər komandaya digərlərindən fərqləndirmək üçün $1$ -dən $2^{30} - 1$ 2^{30} - 1-ə qədər olan diapazonda unikal tam ədəd identifikator verilir.

Superbull elimasiya (kiminin çıxdığı) turniridir. Hər oyundan sonra Fermer Con iki komandadan birini seçib turnirdən çıxarır və çıxarılan komanda artıq sonrakı oyunlarda iştirak edə bilmir. Turnir yalnız bir komanda qaldıqda sona çatır.

Fermer Con bu matçların nəticələrində çox qeyri-adi bir xüsusiyyət müşahidə edir. Hər oyunda iki komandanın topladığı ümumi xal sayı bu komandaların identifikatorları üzərində bitwise istisna VƏ YA (XOR) əməliyyatına bərabərdir. Məsələn, əgər $12$ və $20$ komandaları bir-biri ilə oynasa, oyunda $24$ xal qazanılacaq, çünki $01100 XOR 10100 = 11000$ 01100 \mathbin{\text{ XOR }} 10100 = 11000.

Fermer Con hesab edir ki, oyunda nə qədər çox xal qazanılırsa, o bir o qədər maraqlı olur. Buna görə də o, bütün turnir ərzində toplanan ümumi xal sayının mümkün qədər böyük olması üçün oyunların ardıcıllığını seçmək istəyir. Fermer Cona matçları təşkil etməkdə kömək edin.

Giriş

Birinci sətirdə bir tam ədəd $n (1 \leq n \leq 2000)$ n~(1 \le n \le 2000) verilir. Növbəti $n$ sətirdə hər birində bir komanda identifikatoru verilir.

Çıxış

Superbull turnirində qazanıla biləcək maksimum ümumi xal sayını çıxarın.

Nümunələr

Ümumilikdə $37$ xal qazanmağın bir yolu belədir. Əvvəlcə FC $3$ və $9$ komandalarını qarşılaşdırır və $9$ komandasının qalib gəlməsinə qərar verir, bundan sonra turnirdə $6$ , $9$ və $10$ komandaları qalır. Sonra o, $6$ və $9$ komandalarını qarşılaşdırır və $6$ komandasının qalib gəlməsinə icazə verir. İndi turnirdə $6$ və $10$ komandaları qalır. Nəhayət, $6$ və $10$ komandaları bir-biri ilə qarşılaşır və $10$ komandası qalib gəlir.

Qazanılan ümumi xal sayı bərabərdir

(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

Nümunə 1

Qeyd

Bitwise istisna VƏ YA (XOR) əməliyyatı, adətən $\oplus$ simvolu ilə işarə olunur, — iki ikilik ədədin hər bir uyğun bit cütünə məntiqi istisna VƏ YA əməliyyatını tətbiq edən bitwise əməliyyatdır. Hər mövqedə nəticə, əgər iki bitdən düz biri $1$ -dirsə $1$ -ə, əgər hər iki bit $0$ və ya hər iki bit $1$ -dirsə $0$ -a bərabərdir.

Məsələn,

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