You have an array $a$ of $n$ elements. There are also $q$ modifications of the array. Before the first modification and after each modification, you would like to know the following:

What is the minimum length subarray that needs to be sorted in non-decreasing order in order for the array $a$ to be completely sorted in non-decreasing order?

More formally, you want to select a subarray of the array $(l, r)$ with the minimum value of $r - l + 1$. After that, you will sort the elements $a_{l}, a_{l + 1}, \ldots, a_{r}$ and want the condition $a_{i} \le a_{i + 1}$ to hold for all $1 \le i < n$. If the array is already sorted in non-decreasing order, then $l$ and $r$ should be considered as equal to $-1$.

Note that finding such $(l, r)$ does not change the array in any way. The modifications themselves take the form: assign $a_{pos} = x$ for given $pos$ and $x$.

Input

Each test consists of several test cases. The first line contains an integer $t$ ($1 \le t \le 10$) — the number of test cases. Then follows the description of test cases.

The first line of each test case contains a single integer $n$ ($1 \le n \le 5 \cdot 10^{5}$).

The second line of each test case contains $n$ integers $a_{i}$ ($0 \le |a_{i}| \le 10^{9}$) — the initial elements of the array $a$.

The third line of each test case contains a number $q$ ($0 \le q \le 5 \cdot 10^{5}$) — the number of modifications to the array.

The following $q$ lines of each test case contain two integers $pos_{i}$ ($1 \le pos_{i} \le n$) and $val_{i}$ ($0 \le |val_{i}| \le 10^{9}$) — this means that for the $i$-th modification, $a_{pos_{i}}$ is assigned the value $val_{i}$.

It is guaranteed that the sum of $n$ and the sum of $q$ for all test cases does not exceed $5 \cdot 10^{5}$.

Output

For each test case, output $q + 1$ lines. Each line should contain $2$ integers $l, r$ — the boundaries of the minimum subarray, such that sorting it will make the array $a$ completely sorted. If $a$ is already sorted, then output $l = -1$, $r = -1$.

见题面 Input 部分

见题面 Output 部分

Let's consider the first test case:

• Initially, the array is sorted in non-decreasing order: $[2, 2, 3, 4, 5]$
• After the first query, the array looks like this: $[\color{red}{2}, \color{red}{1}, 3, 4, 5]$.
• After the second query, the array looks like this: $[\color{red}{2}, \color{red}{1}, \color{red}{3}, \color{red}{1}, 5]$.
• After the third query, the array looks like this: $[1, 1, \color{red}{3}, \color{red}{1}, 5]$.

The red segments indicate the subarrays that need to be sorted in order for the entire array to be sorted in non-decreasing order.