Вам дана перестановка \(p\) целых чисел от \(0\) до \(n-1\) (каждое из них встречается ровно один раз). Первоначально перестановка не отсортирована (то есть, \(p_i>p_{i+1}\) хотя бы для одного \(1 \le i \le n - 1\)).
Перестановка называется \(X\)-сортируемой для некоторого неотрицательного целого числа \(X\), если можно отсортировать перестановку, выполнив операцию ниже некоторое конечное число раз:
- Выберите два индекса \(i\) и \(j\) \((1 \le i \lt j \le n)\) такие, что \(p_i \& p_j = X\).
- Поменяйте местами \(p_i\) и \(p_j\).
Здесь \(\&\) обозначает операцию побитового И.
Найдите максимальное значение \(X\) такое, что \(p\) является \(X\)-сортируемой. Можно показать, что всегда существует некоторое значение \(X\) такое, что \(p\) является \(X\)-сортируемой.
Выходные данные
Для каждого набора входных данных выведите одно целое число — максимальное значение \(X\) такое, что \(p\) является \(X\)-сортируемой.
Примечание
В первом наборе входных данных единственными \(X\), для которых перестановка является \(X\)-сортируемой, являются \(X = 0\) и \(X = 2\), максимальный из которых равен \(2\).
Сортировка с использованием \(X = 0\):
- Поменять местами \(p_1\) и \(p_4\), \(p = [2, 1, 3, 0]\).
- Поменять местами \(p_3\) и \(p_4\), \(p = [2, 1, 0, 3]\).
- Поменять местами \(p_1\) и \(p_3\), \(p = [0, 1, 2, 3]\).
Сортировка с использованием \(X = 2\):
- Поменять местами \(p_3\) и \(p_4\), \(p = [0, 1, 2, 3]\).
Во втором наборе входных данных мы должны поменять местами \(p_1\) и \(p_2\), что возможно только при \(X = 0\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
4
0 1 3 2
2
1 0
7
0 1 2 3 5 6 4
5
0 3 2 1 4
|
2
0
4
1
|