#P5259. [CERC2017] Intrinsic Interval

    ID: 4297 传统题 1000ms 512MiB 尝试: 92 已通过: 50 难度: 8 上传者: 标签>CF2500提高+/省选-离线查询懒标记线段树二叉堆扫描中维护贡献

[CERC2017] Intrinsic Interval

题目描述

对于正整数 1,2,3⋯n1,2,3 \cdots n 的一个排列 π\pi,若它的一个子串 π[a..b]\pi[a..b] 排序后是连续正整数,则称 π[a..b]\pi[a..b] 是一个“区间”。例如对排列 pi=3,1,7,5,6,4,2pi={3,1,7,5,6,4,2},子串 π[3..6]\pi[3..6] 是一个“区间”(因为它包含 4,5,6,74,5,6,7),π[1..3]\pi[1..3] 则不是。

一个子串的“本征区间”是包含该子串的最短区间。“包含”是指:若 π[x..y]\pi[x..y] 的本征区间是 π[a..b]\pi[a..b],则 a≤x≤y≤ba \le x \le y \le b。

给定一个排列 π\pi 及其 mm 个子串,求每个子串的“本征区间”。

输入格式

第一行一个整数 n(1≤n≤100000)n(1 \le n \le 100000)。

第二行 nn 个整数,代表排列 π\pi。

第三行一个整数 m(1≤m≤100000)m(1 \le m \le 100000)。

此后 mm 行,每行两个整数 x,y(1≤x≤y≤n)x,y(1 \le x \le y \le n),代表子串 π[x..y]\pi[x..y]。

输出格式

输出 mm 行,每行两个整数 a,b(1≤a≤b≤n)a,b(1 \le a \le b \le n),代表子串对应的本征区间 π[a..b]\pi[a..b]。

输入输出样例 #1

输入 #1

7
3 1 7 5 6 4 2
3
3 6
7 7
1 3

输出 #1

3 6
7 7 
1 7

输入输出样例 #2

输入 #2

10
2 1 4 3 5 6 7 10 8 9
5
2 3
3 7
4 7
4 8
7 8

输出 #2

1 4
3 7
3 7
3 10
7 10