You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.5 seconds
Memory limit: 256.0 MB

# Problem
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 Format
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 Format
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$$$.

## Examples
```input
2
5
2 2 3 4 5
3
2 1
4 1
1 1
5
1 2 3 4 5
9
1 4
2 3
5 2
3 1
1 1
5 1
4 1
3 1
2 1
```
```output
-1 -1
1 2
1 4
3 4
-1 -1
1 3
1 3
1 5
1 5
2 5
2 5
2 5
2 5
-1 -1
```

## Note
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.

Now solve the problem and return the code.