E. Гончар Федор
ограничение по времени на тест
2.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Федя обожает задачи на структуры данных. Особенно он любит задачи про запросы различных функций на подотрезках массива. А именно, у Феди был прекрасный массив $$$a_1, a_2, \ldots a_n$$$, а также замечательная структура данных, которая позволяла по данным $$$l$$$ и $$$r$$$, $$$1 \le l \le r \le n$$$, находить такое максимальное положительное целое число $$$d$$$ такое, что $$$d$$$ является делителем каждого из чисел $$$a_l$$$, $$$a_{l+1}$$$, ..., $$$a_{r}$$$.

Федя очень любил свою структуру данных, поэтому он воспользовался ей для каждого отрезка массива $$$a$$$ и выписал полученные числа в массив, который Федя сразу же отсортировал по неубыванию. Полученный массив он, недолго думая, назвал $$$b$$$. Нетрудно заметить, что массив $$$b$$$ состоял из $$$n(n+1)/2$$$ элементов.

После этого Федя взял еще одну замечательную структуру данных, которая позволяла по данным $$$l$$$ и $$$r$$$, $$$1 \le l \le r \le n(n+1)/2$$$, находить сумму $$$b_l + b_{l+1} + \ldots + b_r$$$. Конечно же, Федя сразу же воспользовался второй структурой данных для каждого отрезка массива $$$b$$$, а полученный массив отсортировал по неубыванию. Тщательно выбирая имя, он назвал полученный массив $$$c$$$. Помогите Феде найти нижнюю медиану массива $$$c$$$.

Напомним, что для отсортированного массива длины $$$k$$$ нижней медианой называется элемент, который стоит на позиции $$$\lfloor \frac{k + 1}{2} \rfloor$$$, с учетом того, что элементы массива нумеруются с $$$1$$$. К примеру, нижней медианой массива $$$(1, 1, 2, 3, 6)$$$ является число $$$2$$$, а нижней медианой массива $$$(0, 17, 23, 96)$$$ — число $$$17$$$.

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

Первая строка входных данных содержит одно целое число $$$n$$$ — количество элементов в массиве $$$a$$$ ($$$1 \le n \le 50\,000$$$).

Вторая строка входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ — элементы массива ($$$1 \le a_i \le 100\,000$$$).

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

Выведите одно число — нижнюю медиану массива $$$c$$$.

Примеры
Входные данные
2
6 3
Выходные данные
6
Входные данные
2
8 8
Выходные данные
8
Входные данные
5
19 16 2 12 15
Выходные данные
12
Примечание

В первом примере массив $$$b$$$ примет вид $$${3, 3, 6}$$$, массив $$$c$$$ примет вид $$${3, 3, 6, 6, 9, 12}$$$, а искомая нижняя медиана равна $$$6$$$.

В втором примере массив $$$b$$$ примет вид $$${8, 8, 8}$$$, массив $$$c$$$ примет вид $$${8, 8, 8, 16, 16, 24}$$$, а искомая нижняя медиана равна $$$8$$$.