Batman Returns

문제

Gotham City consists of a single street, and there are $nn$ skyscrapers located along it. They are numbered from west to east with integers from $11$ to $nn$, the height of the $ii$-th skyscraper is equal to $h_{i}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 $qq$ to skyscraper $pp$ if and only if and . Moreover, Batman is very manoeuvrable, so the height of the buildings between $pp$ and $qq$ don't matter. Batman cares a lot about the crime level in the city so he chooses such pair of valid $pp$ and $qq$ that $q-pq\; -\; p$ is maximum possible.

City authorities have developed $mm$ plans of city renewal. According to the $ii$-th plan only skyscrapers from $l_{i}l\_i$ to $r_{i}r\_i$, inclusive will remain on this street, while others will be destroyed. For each plan $ii$ Batman wants to know the optimal plan to observe the city, namely such $p_{i}p\_i$ and $q_{i}q\_i$ that , and $q_i-p_{i}q\_i\; -\; p\_i$ is maximum possible.

입력

The first line of the input contains one integer $nn$ ($1\le n\le 2000001\; \backslash le\; n\; \backslash le\; 200\backslash ,000$) --- number of skyscrapers on the street.

The second line contains $nn$ integers $h_{i}h\_i$($1\le h_i\le 2000001\; \backslash le\; h\_i\; \backslash le\; 200\backslash ,000$) --- heights of the skyscrapers.

Third line contains integer $mm$ ($1\le m\le 2000001\; \backslash le\; m\; \backslash le\; 200\backslash ,000$) --- the number of plans designed by the city authorities.

Each of the last $mm$ lines contains two integers $l_{i}l\_i$ and $r_{i}r\_i$ (), denoting the range of the skyscrapers that will remain according to the $ii$-th plan.

출력

For each renewal plan you should print two integers --- optimal $p_{i}p\_i$ and $q_{i}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 $33$ and $11$ but they are not valid since $3\ge 13\; \backslash geq\; 1$. In the second query the pair consisting of the first and the second skyscrapers is valid since they have heights $22$ and $33$.

Consider the second sample test. In the first query the pair of skyscrapers with heights $22$ and $33$, and the pair of skyscrapers with heights $22$ and $44$ are valid. The distance between first two of them is greater so this pair produces the answer for this query.