Fedya the Potter

题意翻译

- 给定一个长度为 $n$ 的序列 $a_i$，对于每个区间 $[l,r]$，$\gcd(a_l,a_{l+1},\cdots,a_r)$ 被记录到一个数组 $b_i$ 里，然后 $b_i$ 从大到小排序之后的所有不同区间的区间和为数组 $c_i$，求 $c_i$ 的中位数。 - 对于 $100\%$ 的数据，$1 \le n \le 5 \times 10^4$，$1 \le a_i \le 10^5$。 - 翻译者：一只书虫仔。

题目描述

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 $ .

输入输出格式

输入格式

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 $ ).

输出格式

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

输入输出样例

输入样例 #1

2
6 3

输出样例 #1

6

输入样例 #2

2
8 8

输出样例 #2

8

输入样例 #3

5
19 16 2 12 15

输出样例 #3

12

说明

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 $ .