Fedya 喜欢涉及数据结构的问题。特别是关于子分段的不同查询。 Fedya 有一个很好的数组 $$$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}$$$。
Fedya非常喜欢这个数据结构,因此他将其应用于数组$$$a$$$的每个非空连续子数组,将所有答案放入数组中并排序。他称这个数组为$$$b$$$。很容易看出数组 $$$b$$$ 包含 $$$n(n+1)/2$$$ 元素。
之后,Fedya 实现了另一个很酷的数据结构,这使他能够针对给定的 $$$l$$$ 和 $$$r$$$ 求和 $$$b_l + b_{l+1} + \ldots + b_r$$$,$$$1 \le l \le r \le n(n+1)/2$$$。当然,Fedya 将此数据结构应用于数组 $$$b$$$ 的每个连续子数组,调用结果 $$$c$$$ 并将其排序。帮助 Fedya 找到数组 $$$c$$$ 的下中位数。
回想一下,对于长度为 $$$k$$$ 的排序数组,如果数组的元素是从 $$$1$$$ 开始枚举的,则下中位数是位置 $$$\lfloor \frac{k + 1}{2} \rfloor$$$ 处的元素。例如,数组 $$$(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$$$ 的下中位数。
示例
输入 #1
2 6 3
输出 #1
6
输入 #2
2 8 8
输出 #2
8
输入 #3
5 19 16 2 12 15
输出 #3
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$$$。