题目描述

给定一个$1\sim n$的排列$a_1,…,a_n$。 对于一个区间$[l,r]$，我们称该区间是连续的，如果将$a_l,…,a_r$排序之后得到的是一列连续的数。（换句话说，如果$x,y$都在该区间中，那么所有介于$x,y$之间的数也在该区间中） 现在有$m$个询问，每个询问给出一个区间$[x_i,y_i]$，你需要找到一个长度最短的连续区间$[l_i,r_i]$，使得$[x_i,y_i]⊆[l_i,r_i]$。

输入

第1行$1$个数$n$。 第2行$n$个数$a_1,…,a_n$。 第3行$1$个数$m$。 第4行到第$m+3$行，每行$2$个数$x_i,y_i$。

输出

输出共$m$行，每行两个数$l_i,r_i$，含义如题目中所述。

输入样例

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

输出样例

3 6
7 7
1 7

提示

【数据规模】 对于30%的数据：$1≤n,m≤1000$。 对于另外40%的数据：$y_i=x_i+1$。 对于100%的数据：$1≤n,m≤100000$，$1≤x_i≤y_i≤n$，$a_1,…,a_n$为$1\sim n$的排列。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共5个测试点，非原站或官方原始数据。总分100分。