Two Kilers

Jurek Kiler, the main character of the Polish movie Two Kilers, receives regular deliveries of gold boxes. The value of the $i$-th delivery is $c_i$, the total value of the gold boxes inside it.

Recently Jurek has become concerned that the values of the deliveries are falling. To check this, he defined a measure for a sequence of deliveries called the disorder of the sequence. For an integer sequence $c_1, c_2, \ldots, c_n$, the disorder is the length of its longest strictly increasing subsequence. Formally, it is the largest integer $s$ such that there are indices $i_1 < i_2 < \ldots < i_s$ with $c_{i_1} < c_{i_2} < \ldots < c_{i_s}$.

If the disorder is at least $k$, Jurek considers his concern unfounded and does not need the exact value. Some gold boxes are stolen, and some arrive late in large batches, so the delivery values can change. After each change, compute the disorder, or output $k$ if the disorder is at least $k$.

The first line contains one integer $Z \le 10$, the number of test cases.

Each test case starts with a line containing two integers $n$ and $k$, the number of deliveries and the parameter $k$. The next line contains $n$ integers $c_1, c_2, \ldots, c_n$, the initial delivery values. The next line contains one integer $q$, the number of value changes. Each of the following $q$ lines contains two integers $p_j$ and $v_j$, meaning that $c_{p_j} = v_j$.

For each test case, output $q$ lines, each containing one natural number. If the disorder after the $j$-th change is $s$, output $\min(s, k)$ on the $j$-th line.

$n, q \in [1, 10^5]$

$c_i, v_j \in [1, 10^9]$

$p_j \in [1, n]$

$k \in [1, 20]$