C. XOR-инверсии
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задан массив $$$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$$$ несколько — выведите минимальное из них.

Входные данные

Первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — количество элементов в массиве $$$a$$$.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$0 \le a_i \le 10^9$$$), где $$$a_i$$$ — $$$i$$$-й элемент $$$a$$$.

Выходные данные

Выведите два целых числа: минимально возможное количество инверсией в массиве $$$b$$$, и минимальное значение $$$x$$$, при котором достигается такое количество инверсий.

Примеры
Входные данные
4
0 1 3 2
Выходные данные
1 0
Входные данные
9
10 7 9 10 7 5 5 3 5
Выходные данные
4 14
Входные данные
3
8 10 3
Выходные данные
0 8
Примечание

В первом примере из условия оптимально оставить массив без изменений, выбрав $$$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]$$$. В нем нет ни одной инверсии.