Вам дан массив \(a\) длины \(n\). Вы можете применить следующую операцию несколько (возможно, ноль) раз:
- Выбрать \(i\), \(j\), \(b\): Поменять местами \(b\)-й бит в бинарной записи \(a_i\) и \(a_j\).
В бинарной записи биты нумеруются справа (наименее значимый) налево (наиболее значимый). Учтите, что в начале любой бинарной записи имеется бесконечное число начальных нулевых битов.
Например, поменять местами \(0\)-й бит для \(4=100_2\) и \(3=11_2\) даст в результате \(101_2=5\) и \(10_2=2\). Поменять местами \(2\)-й бит для \(4=100_2\) и \(3=11_2\) даст в результате \(000_2=0_2=0\) и \(111_2=7\).
Найдите максимальное значение \(\max(a) - \min(a)\).
Тут \(\max(a)\) означает максимальный элемент \(a\) и \(\min(a)\) означает минимальный элемент \(a\).
Бинарная запись \(x\) — это \(x\) записанное в системе счисления с основанием \(2\). Например, \(9\) и \(6\) записанные в системе счисления с основанием \(2\) это \(1001\) и \(110\), соответственно.
Выходные данные
Для каждого набора входных данных выведите одно целое число — максимальное возможное значение \(\max(a) - \min(a)\).
Примечание
В первом примере может быть показано, что не надо делать никаких операций — максимальное значение \(\max(a) - \min(a)\) это \(1 - 0 = 1\).
Во втором примере ни одна операция не может изменить массив — максимальное значение \(\max(a) - \min(a)\) это \(5 - 5 = 0\).
В третьем примере изначально \(a = [1, 2, 3, 4, 5]\), мы можем применить операцию \(i = 2\), \(j = 5\), \(b = 1\). Массив станет равен \(a = [1, 0, 3, 4, 7]\). Может быть показано, что последующие операции не приведут к улучшению ответ. Таким образом, максимальное значение это \(\max(a) - \min(a) = 7 - 0 = 7\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
3
1 0 1
4
5 5 5 5
5
1 2 3 4 5
7
20 85 100 41 76 49 36
|
1
0
7
125
|