30818번 - Batman Returns 스페셜 저지다국어

문제

Gotham City consists of a single street, and there are $n$ skyscrapers located along it. They are numbered from west to east with integers from 1ドル$ to $n,ドル the height of the $i$-th skyscraper is equal to $h_i$ meters.

Every night Batman performs an observation flight over the city. He climbs on the roof of some skyscraper and glides down to the roof of some other skyscraper. Due to the strong permanent wind he is only able to flight westward, but his altitude remains almost the same. Thus, he is able to glide down from skyscraper $q$ to skyscraper $p$ if and only if $p < q$ and $h_p < h_q$. Moreover, Batman is very manoeuvrable, so the height of the buildings between $p$ and $q$ don't matter. Batman cares a lot about the crime level in the city so he chooses such pair of valid $p$ and $q$ that $q - p$ is maximum possible.

City authorities have developed $m$ plans of city renewal. According to the $i$-th plan only skyscrapers from $l_i$ to $r_i,ドル inclusive will remain on this street, while others will be destroyed. For each plan $i$ Batman wants to know the optimal plan to observe the city, namely such $p_i$ and $q_i$ that $l_i \leq p_i < q_i \leq r_i,ドル $h_{p_i} < h_{q_i}$ and $q_i - p_i$ is maximum possible.

입력

The first line of the input contains one integer $n$ (1ドル \le n \le 200,000円$) --- number of skyscrapers on the street.

The second line contains $n$ integers $h_i$(1ドル \le h_i \le 200,000円$) --- heights of the skyscrapers.

Third line contains integer $m$ (1ドル \le m \le 200,000円$) --- the number of plans designed by the city authorities.

Each of the last $m$ lines contains two integers $l_i$ and $r_i$ (1ドル \leq l_i < r_i \leq n$), denoting the range of the skyscrapers that will remain according to the $i$-th plan.

출력

For each renewal plan you should print two integers --- optimal $p_i$ and $q_i$. If there is no possible observation flight at all, you should print -1 -1.

If there are many optimal answers, you may print any one of them.

제한

노트

Consider the first sample test. In the first query the only two available skyscrapers have heights 3ドル$ and 1ドル$ but they are not valid since 3ドル \geq 1$. In the second query the pair consisting of the first and the second skyscrapers is valid since they have heights 2ドル$ and 3ドル$.

Consider the second sample test. In the first query the pair of skyscrapers with heights 2ドル$ and 3ドル,ドル and the pair of skyscrapers with heights 2ドル$ and 4ドル$ are valid. The distance between first two of them is greater so this pair produces the answer for this query.