대포

어떤 왕국이 전쟁을 준비하고 있다. 이 왕국의 군대는 주로 대포로 이루어져 있으며, 대포를 이용한 전투 전술은 매우 단순하다. 왕국은 $n$문의 대포를 보유하고 있다. 전투 중에는 대포들을 전선을 따라 일렬로 배치한다. 대포에는 왼쪽에서 오른쪽으로 $1$번부터 $n$번까지 차례로 번호가 매겨진다. $i$번 대포에는 그 전투력을 나타내는 정수 $p_i$가 부여되어 있다.

왕립 전투 분석 센터(CAB)는 전투 전술을 담당한다. 전쟁을 준비하면서 CAB는 여러 전투 시나리오를 검토한다. 하나의 시나리오는 전선의 $a$번 대포부터 $b$번 대포까지의 구간이 공격받는 상황을 가정한다. 가장 효과적인 전술을 세우기 위해, CAB는 해당 구간에 있는 대포들의 최소 전투력과 최대 전투력을 알아야 한다. CAB가 이 문제를 빠르게 해결할 수 있도록 도와라.

첫째 줄에 테스트의 개수를 나타내는 자연수 $d$ ($1 \le d \le 100$)가 주어진다. 각 테스트의 설명은 다음 줄들에 차례로 이어진다.

각 테스트의 첫째 줄에는 대포의 개수를 나타내는 정수 $n$ ($1 \le n \le 10^6$)이 주어진다. 둘째 줄에는 $n$개의 정수 $p_i$ ($-10^9 \le p_i \le 10^9$)가 주어지며, 이는 각 대포의 전투력이다. 그 다음 줄에는 CAB가 검토하는 시나리오의 개수 $m$ ($1 \le m \le 10^5$)이 주어진다. 이어지는 $m$개의 줄에는 각 시나리오가 주어진다. 각 시나리오는 두 정수 $a$와 $b$ ($1 \le a \le b \le n$)로 이루어진다.

각 시나리오에 대해, $a$번 대포부터 $b$번 대포까지의 구간에 있는 대포들의 최소 전투력과 최대 전투력을 한 줄에 공백으로 구분하여 출력한다.