UOJ Logo

NOI.AC

1S 512MB
Statistics

Description

给出一个长度为$n$的排列

定义连续区间为该区间$[l,r]$所包含的数$a_l,a_{l+1},...,a_{r}$可以恰好落在某个$[x,x+r-l]$内

给出$m$个询问

每次询问一个区间$[l,r]$,问最小(即长度最短)包含这个区间的连续区间是什么,如果有多个解输出左端点靠前的

Input

第一行一个整数$n$,如题所述

第二行$n$个整数,分别表示$a_1,a_2,a_3,...,a_n$

第三行一个整数$m$,如题所述

接下来$m$行每行两个整数$l,r$,如题所述

Output

$m$行每行两个整数表示答案

Sample Input

7

3 1 7 5 6 4 2

3

3 6

7 7

1 3

Sample Output

3 6

7 7

1 7

Constraints

本题使用Subtask评测

Subtask1(10pts): $n,m\leq 100$

Subtask2(40pts): $n,m\leq 5000$

Subtask3(50pts): $n,m\leq 100000$