배트맨 리턴즈

고담 시는 하나의 거리로 이루어져 있고, 그 거리를 따라 $n$개의 고층 빌딩이 늘어서 있다. 빌딩은 서쪽에서 동쪽으로 $1$번부터 $n$번까지 번호가 매겨져 있으며, $i$번째 빌딩의 높이는 $h_i$미터이다.

매일 밤 배트맨은 도시 상공을 비행한다. 그는 한 빌딩의 옥상에 올라 다른 빌딩의 옥상으로 활강한다. 강한 바람이 늘 불고 있어서 그는 서쪽으로만 날 수 있고, 고도는 거의 변하지 않는다. 따라서 $p < q$이고 $h_p < h_q$일 때에만 빌딩 $q$에서 빌딩 $p$로 활강할 수 있다. 배트맨은 매우 기동성이 좋아서 $p$와 $q$ 사이에 있는 빌딩의 높이는 신경 쓰지 않는다. 배트맨은 도시의 범죄 수준을 중요하게 여기므로, 유효한 쌍 $p$, $q$ 가운데 $q - p$가 가장 큰 쌍을 고른다.

시 당국은 $m$개의 재개발 계획을 세웠다. $i$번째 계획에서는 $l_i$번부터 $r_i$번까지의 빌딩만 남고 나머지는 모두 철거된다. 각 계획 $i$에 대해 $l_i \le p_i < q_i \le r_i$, $h_{p_i} < h_{q_i}$를 만족하면서 $q_i - p_i$가 최대가 되는 $p_i$, $q_i$를 구하라.

첫째 줄에 빌딩의 수 $n$ ($1 \le n \le 200\,000$)이 주어진다. 둘째 줄에는 빌딩의 높이 $h_i$ ($1 \le h_i \le 200\,000$)가 $n$개 주어진다. 셋째 줄에는 계획의 수 $m$ ($1 \le m \le 200\,000$)이 주어진다. 이어지는 $m$개의 줄에는 각각 두 정수 $l_i$, $r_i$ ($1 \le l_i < r_i \le n$)가 주어지며, 이는 $i$번째 계획에서 남는 빌딩의 범위이다.

각 계획마다 최적의 쌍 $p_i$, $q_i$를 두 정수로 출력한다. 유효한 비행이 하나도 없으면 $-1$ $-1$을 출력한다. 최적해가 여러 개라면 그중 아무것이나 출력해도 된다.

첫 번째 샘플을 보자. 첫 번째 질의에서 쓸 수 있는 빌딩은 높이 3과 1인 두 개뿐인데, $3 \ge 1$이므로 유효하지 않다. 두 번째 질의에서는 1번 빌딩과 2번 빌딩의 쌍이 유효하며, 두 빌딩의 높이는 각각 2와 3이다.

두 번째 샘플을 보자. 첫 번째 질의에서 높이 2와 3인 쌍과 높이 2와 4인 쌍이 모두 유효하다. 앞의 쌍이 거리가 더 멀므로 이 질의의 답이 된다.