Вам задан массив \(a\), состоящий из \(n\) неотрицательных целых чисел. Вы должны выбрать неотрицательное целое число \(x\) и сформировать массив \(b\) из \(n\) элементов по следующему правилу: для всех \(i\) от \(1\) до \(n\), \(b_i = a_i \oplus x\) (\(\oplus\) обозначает операцию побитового исключающего ИЛИ).
Назовем инверсией в массиве \(b\) такую пару целых чисел \(i\) и \(j\), что \(1 \le i < j \le n\) и \(b_i > b_j\).
Вы должны выбрать \(x\) таким образом, чтобы количество инверсий в массиве \(b\) было минимально возможным. Если таких \(x\) несколько — выведите минимальное из них.
Выходные данные
Выведите два целых числа: минимально возможное количество инверсией в массиве \(b\), и минимальное значение \(x\), при котором достигается такое количество инверсий.
Примечание
В первом примере из условия оптимально оставить массив без изменений, выбрав \(x = 0\).
Во втором примере из условия при выборе \(x = 14\) получается следующий массив \(b\): \([4, 9, 7, 4, 9, 11, 11, 13, 11]\). В нем \(4\) инверсии:
- \(i = 2\), \(j = 3\);
- \(i = 2\), \(j = 4\);
- \(i = 3\), \(j = 4\);
- \(i = 8\), \(j = 9\).
В третьем примере из условия при выборе \(x = 8\) получается следующий массив \(b\): \([0, 2, 11]\). В нем нет ни одной инверсии.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
0 1 3 2
|
1 0
|
|
2
|
9
10 7 9 10 7 5 5 3 5
|
4 14
|
|
3
|
3
8 10 3
|
0 8
|