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$