Migrated from Lutece 2564 羽毛球赛

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$ 位选手，每位选手会被分配一个编号 $d$ ，可以相同。选手等距 $1$ 米的排成一排，只能把球打给与自己编号相同的人。没有与自己编号相同的选手计 $0$ 分。

裁判在每场比赛中划出一个区间范围，在这个范围内的选手需要把自己的球打向在这个区间内的与自己编号相同，且离自己距离最远的人，因为羽毛球飞过的水平距离越远，得分越高。得分为羽毛球飞过的水平距离（忽略人的大小）。

现在进行 $m$ 场比赛，请问每场比赛中最高分是多少。

Input

第 $1$ 行一个整数 $n$，表示选手数量。

第 $2$ 行 $n$ 个整数，从左到右给出每个选手的编号 $d$。

第 $n+1$ 行一个整数 $m$ ，表示比赛场数。

第 $n+2\sim n + m+1$ 行，每行两个整数 $l,r$ 表示每场比赛中划出的区间范围。

Output

共 $m$ 行，每行一个整数表示答案。

Samples

5
1 2333 2334 2333 1
3
1 3
2 4
1 5

0
2
4

Constraints

$1 \le n, m \le 2 \cdot 10^5,0\leq d \leq 2 \cdot 10^9, 1 \le l \le r \le n$

Resources

2021 UESTC ICPC Training for Data Structures