提示: 欢迎访问OurACM平台。
Problem 2226 信心题

Accept: 99    Submit: 423
Time Limit: 2000 mSec    Memory Limit : 32768 KB

Problem Description

给定一个含有n个数字的数列,每个数字都有一个值a[i](下标从1开始)。定义第i个数字和第j个数字间的距离dis(i,j)=abs(i-j)。

接下来给出q个询问,每次询问一个区间[l,r],要求求出一对数字(i,j)(l<=i<=j<=r),使得a[i]=a[j]并且dis(i,j)最大,由于这样的数对可能有多个,因此答案只要输出dis。

Input

题目包含多组数据

每组数据第一行一个数n

第二行n个数字,表示数列a

第三行一个数字q,表示询问个数

接下来q行,每行两个数l,r,表示询问

N<=10^5

Q<=10^4

1<=a[i]<=10^3

1<=l<=r<=n

Output

每个询问输出一个数组dis

Sample Input

5 1 2 3 1 2 3 3 3 2 5 1 5

Sample Output

0 3 3

Source

FOJ有奖月赛-2016年4月(校赛热身赛)

Submit  Back  Status  Discuss