Задача . E. Гончар Федор

Федя обожает задачи на структуры данных. Особенно он любит задачи про запросы различных функций на подотрезках массива. А именно, у Феди был прекрасный массив \(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\).