--- tags: 問題 --- # D - XOR Rally 実行時間制限 : 2sec / メモリ制限 : 1024MB 配点 : $400$点 元ネタ : [ABC156 C-Rally](https://atcoder.jp/contests/abc156/tasks/abc156_c) ## 問題文 数直線上に$N$人の人が住んでいます。 $i$番目の人が住んでいるのは座標 $X_i$です。 あなたは$N$人全員が参加する集会を開くことを考えています。 集会は数直線上の任意の**非負整数値の座標**で開くことができ、座標$P$で集会を開くとき、$i$番目の人は集会に参加するために$X_i$と$P$の**排他的論理和**だけの体力を消費します。 $N$人が消費する体力の総和としてありえる値の最小値を求めてください。 ## 制約 * $1\leq N \leq 2×10^5$ * $0 \leq X_i \leq 10^9$ 入力はすべて正の整数 ## 入力 入力は以下の形式で標準入力から与えられる。 ``` N X_1 X_2 ... X_N ``` ## 出力 $N$人が消費する体力の総和としてありえる値の最小値を出力せよ。 ## 入力例1 ``` 5 5 10 8 7 2 ``` ## 出力例1 ``` 30 ``` ## 入力例2 ``` 3 0 0 0 ``` ## 出力例2 ``` 0 ``` 同居している人もいるかもしれませんし、誰かの家で集会を開くこともあります。 ## 入力例3 ``` 10 1 2 3 4 5 6 7 8 9 10 ``` ## 出力例3 ``` 55 ```