CF1098E.Fedya the Potter

Fedya loves problems involving data structures. Especially ones about different queries on subsegments. Fedya had a nice array $a_1, a_2, \ldots a_n$ and a beautiful data structure. This data structure, given $l$ and $r$, $1 \le l \le r \le n$, could find the greatest integer $d$, such that $d$ divides each of $a_l$, $a_{l+1}$, ..., $a_{r}$.

Fedya really likes this data structure, so he applied it to every non-empty contiguous subarray of array $a$, put all answers into the array and sorted it. He called this array $b$. It's easy to see that array $b$ contains $n(n+1)/2$ elements.

After that, Fedya implemented another cool data structure, that allowed him to find sum $b_l + b_{l+1} + \ldots + b_r$ for given $l$ and $r$, $1 \le l \le r \le n(n+1)/2$. Surely, Fedya applied this data structure to every contiguous subarray of array $b$, called the result $c$ and sorted it. Help Fedya find the lower median of array $c$.

Recall that for a sorted array of length $k$ the lower median is an element at position $\lfloor \frac{k + 1}{2} \rfloor$, if elements of the array are enumerated starting from $1$. For example, the lower median of array $(1, 1, 2, 3, 6)$ is $2$, and the lower median of $(0, 17, 23, 96)$ is $17$.

费迪亚喜欢涉及数据结构的题目，尤其是关于子数组上各类查询的问题。费迪亚有一个优美的数组 $a_1, a_2, \ldots, a_n$ 和一个漂亮的数据结构。该数据结构在给定 $l$ 和 $r$（其中 $1 \le l \le r \le n$）时，能求出最大的整数 $d$，使得 $d$ 能整除 $a_l, a_{l+1}, \ldots, 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$ 的下中位数（lower median）。

需要回顾的是：对于一个长度为 $k$ 的已排序数组，其下中位数是位于位置 $\lfloor \frac{k + 1}{2} \rfloor$ 上的元素（数组下标从 $1$ 开始计数）。例如，数组 $(1, 1, 2, 3, 6)$ 的下中位数是 $2$，而 $(0, 17, 23, 96)$ 的下中位数是 $17$。

First line contains a single integer $n$ — number of elements in array $a$ ($1 \le n \le 50\,000$).

Second line contains $n$ integers $a_1, a_2, \ldots, a_n$ — elements of the array ($1 \le a_i \le 100\,000$).

第一行包含一个整数 $n$ —— 数组 $a$ 的元素个数（$1 \le n \le 50\,000$）。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ —— 数组的元素（$1 \le a_i \le 100\,000$）。

Print a single integer — the lower median of array $c$.

输出一个整数——数组 $c$ 的下中位数。

In the first sample array $b$ is equal to ${3, 3, 6}$, then array $c$ is equal to ${3, 3, 6, 6, 9, 12}$, so the lower median is $6$.

In the second sample $b$ is ${8, 8, 8}$, $c$ is ${8, 8, 8, 16, 16, 24}$, so the lower median is $8$.

在第一个样例中，数组 $b$ 为 ${3, 3, 6}$，则数组 $c$ 为 ${3, 3, 6, 6, 9, 12}$，因此下中位数为 $6$。

在第二个样例中，$b$ 为 ${8, 8, 8}$，$c$ 为 ${8, 8, 8, 16, 16, 24}$，因此下中位数为 $8$。