B'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} <= a_{i + 1} to hold for all 1 <= 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 . Each test consists of several test cases. The first line contains an integer t ( 1 <= t <= 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 <= n <= 5 cdot 10^{5} ). The second line of each test case contains n integers a_{i} ( 0 <= |a_{i}| <= 10^{9} ) -- the initial elements of the array a . The third line of each test case contains a number q ( 0 <= q <= 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 <= pos_{i} <= n ) and val_{i} ( 0 <= |val_{i}| <= 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} . For each test case, output q + 1 lines. Each line should contain 2 integ'...