Batman Returns

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

Every night Batman flies over the city. He climbs onto the roof of one skyscraper and glides down to the roof of another. A strong permanent wind means he can only fly westward, and his altitude stays almost the same. So he can glide from skyscraper $q$ to skyscraper $p$ if and only if $p < q$ and $h_p < h_q$. The buildings between $p$ and $q$ do not matter, because Batman is very maneuverable. Batman cares a lot about the crime level in the city, so he picks a valid pair $p$, $q$ with the largest possible $q - p$.

City authorities have drawn up $m$ renewal plans. In plan $i$, only the skyscrapers from $l_i$ to $r_i$, inclusive, remain, and the others are destroyed. For each plan $i$, find $p_i$ and $q_i$ such that $l_i \le p_i < q_i \le r_i$, $h_{p_i} < h_{q_i}$, and $q_i - p_i$ is as large as possible.

The first line contains one integer $n$ ($1 \le n \le 200\,000$), the number of skyscrapers. The second line contains $n$ integers $h_i$ ($1 \le h_i \le 200\,000$), the heights of the skyscrapers. The third line contains one integer $m$ ($1 \le m \le 200\,000$), the number of plans. Each of the last $m$ lines contains two integers $l_i$ and $r_i$ ($1 \le l_i < r_i \le n$), the range that remains in plan $i$.

For each plan, print two integers $p_i$ and $q_i$ for an optimal pair. If no observation flight is possible, print $-1$ $-1$. If several optimal answers exist, print any of them.

Consider the first sample. In the first query, the only two available skyscrapers have heights 3 and 1, but they are not valid because $3 \ge 1$. In the second query, the pair formed by the first and second skyscrapers is valid, since their heights are 2 and 3.

Consider the second sample. In the first query, the pairs with heights 2 and 3 and with heights 2 and 4 are both valid. The first of these pairs is farther apart, so it gives the answer for that query.