F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:本站提供各级各类比赛备战资源(Noip提高组及以下),有意者请联系Lydsy2012@163.com,仅限教师及家长用户。
Problem 5259. -- [Cerc2017]区间

5259: [Cerc2017]区间

Time Limit: 10 Sec  Memory Limit: 512 MB
Submit: 76  Solved: 44
[Submit][Status][Discuss]

Description

给定一个1到n的排列a1, . . . , an。
对于一个区间[l, r],我们称该区间是连续的,如果将al, . . . , ar排列之后得到的是一列连续的数。
(换句话说,如果x,y都在该区间中,那么所有介于x,y之间的数也在该区间中)
现在有m(1 ≤ n, m ≤ 100000)个询问,每个询问给出一个区间[xi, yi],
你需要找到一个长度最短的连续区间[li,ri],使得[xi,yi]属于 [li, ri]。

Input

第1行1个数n。
第2行n个数a1,...an(a1, . . . , an为1到n的排列)。
第3行1个数m。
第4行到第m+3行,每行2个数xi,yi(1 ≤ xi ≤ yi ≤ n)。

Output

输出共m行,每行两个数li,ri,含义如题目所述。

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

HINT

Source

[Submit][Status][Discuss]

HOME Back