Predictor Machine

Seeing how many people wanted to know their future CF rating, Stefan decided to actually use his programming skills to actually find some important points in people’s CF rating graphs. Since he doesn’t have time to add all his charting techniques in the code, he will only deal with points of interest.

Namely, he is given an array of $n$ integers, indexed from $1$, and a continuous function, such that $v_i = f(i)$, which represents someone’s CodeForces rating graph, described as a function. Since the function is continuous, for each line between two consecutive points, the graph of the function touches all the integer points between the values.

For example, if $f(1) = 3$ and $f(2) = 9$, the line will touch the integer points $3$, $4$, $5$, $6$, $7$, $8$ and $9$.

We are also given $q$ queries, where at some query we will change the value of a given position in the array and after each query, we must print the point of interest of this array, which is the point touched the biggest amount of times by the graph of the function; Furthermore, you also have to print how many times it is touched.

If there are multiple such points, we will print the point with the smallest value among them.

It is also guaranteed that the $n$ values will be distinct both at the beginning and throughout the updates.

Input

On the first line you will get $n$, the number of integers from the array ($2 \le n \le 10^5$).

On the second line you will get $n$ distinct integers, representing the array $v$ ($1 \le v_i \le 2 \cdot 10^5$).

On the third line you will get $q$, the number of queries we have to answer to ($1 \le q \le 2 \cdot 10^5$).

On the next $q$ lines you will get two numbers, $pos$ and $val$, representing that $v_{pos}$ becomes $val$.

For tests worth $30$ points, ($1 \le n; q \le 1000$).

Output

The output will contain $q$ lines, each line containing the two integers asked by the problem, namely the leftmost point which is touched the most amount of times by the graph of the function and how many times it is touched after the first $q$ updates have been done.

Example

stdin

5
4 2 6 1 7
5
1 3
4 4
2 1
5 2
3 5

stdout

3 4
5 3
5 3
2 3
2 3

Explanation

After all the updates are done, the array will look like this: 3 1 5 4 2.

The integer $2$ is touched $3$ times, between positions $1$ and $2$, between positions $2$ and $3$ and between positions $4$ and $5$.