CF1098E Fedya the Potter

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}, \ldots, a_r$ 中的每一个数。 Fedya 非常喜欢这个数据结构，于是他对数组 $a$ 的每一个非空连续子数组都应用了一次，把所有的答案放进一个数组并排序，他把这个数组叫做 $b$。很容易看出，数组 $b$ 一共有 $n(n+1)/2$ 个元素。 之后，Fedya 又实现了另一个很酷的数据结构，可以在给定 $l$ 和 $r$，$1 \le l \le r \le n(n+1)/2$ 的情况下，求出 $b_l + b_{l+1} + \ldots + b_r$ 的和。当然，Fedya 又对数组 $b$ 的每一个连续子数组都应用了一次，把所有结果放进一个数组并排序，称这个结果为 $c$。请你帮助 Fedya 找出数组 $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$ 的下中位数。

在第一个样例中，数组 $b$ 等于 $\{3, 3, 6\}$，数组 $c$ 等于 $\{3, 3, 6, 6, 9, 12\}$，所以下中位数是 $6$。 在第二个样例中，$b = \{8, 8, 8\}$，$c = \{8, 8, 8, 16, 16, 24\}$，所以下中位数是 $8$。 由 ChatGPT 4.1 翻译