Migrated from Lutece 2929 Redcrown的数学题

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

本题方法：正统分块

这是一道数学题。

给你一个长度为 $n$ 的序列，第 $i$ 个数为 $a_i$ ，现在希望你选择一个 $i \in [l,r]$ ，记 $p_i$ 表示 $a_i$ 在原序列的 $[l,r]$ 子段中的出现次数，希望你的选择能使得 $a_i \times (n^{p_i}+\frac{1}{n})$ 最大，输出对应的 $a_i$ ，如果有多个 $a_i$ 使得表达式最大，请输出最小的那个 $a_i$ 。

希望你能在线的回答 $q$ 次询问，每次给你的区间 $[l,r]$ 可能不一样。在线不是让你和Redcrown连麦，而是你下一次询问的内容取决于上一次的答案。

Input

第一行一个整数 $n$ ，表示序列长度。

第二行 $n$ 个整数，第 $i$ 个整数为 $a_i$ ，表示给你的序列。

第三行一个整数 $q$ ，表示询问个数。

接下来 $q$ 行每行两个整数 $l_0$ 和 $r_0$ ，这并不一定是询问的区间，我们用下面这种方法获得本次询问区间。

记你上一次询问得到的答案是 $x$ （如果是第一次询问则认为 $x=0$ ），则可以算出两个整数 $l=((l_0+x-1) \bmod n) + 1, r=((r_0+x-1) \bmod n) + 1$ ，若 $r$ 小于 $l$ 则交换 $r$ 和 $l$ ，之后本次询问区间即为 $[l,r]$ 。

Output

输出 $q$ 行，每行一个整数，表示使得表达式值最大的 $a_i$ ，如果有多个这样的 $a_i$ 使得表达式的值最大，请输出最小的 $a_i$ 。

Samples

6
1 1 4 5 1 4
5
1 2
6 2
1 4
2 5
2 3

1
1
1
4
1

2
1 2
1
1 2

2

Constraints

$1 \le n \le 10^5, 1 \le a_i \le n, 1 \le q \le 10^5, 1 \le l_0,\; r_0 \le n$

Note

对于样例1，真正询问的区间分别是 $[1,2]$ ， $[1,3]$ ， $[2,5]$ ， $[3,6]$ ， $[1,6]$ 。

对于样例2，若取 $i=1$ 则表达式的值为 $1\times (2+\frac{1}{2})=2.5$ ，若取 $i=2$ 则表达式的值为 $2\times (2+\frac{1}{2})=5$ ，故选择 $i=2$ 。

Resources

2023 UESTC ICPC Training for Data Structures