23467번 - Two Kilers 다국어

In famous polish movie Two Kilers, main character Jurek Kiler receives regular deliveries of gold boxes. Each delivery can be described by value of gold boxes inside it, value of $i$-th delivery is equal to $c_i$.

Recently Jurek has felt concerned about falling value of deliveries. To check if those values are truly falling, he invented a measurement for sequence of deliveries, he calls it a disorder of a sequence.

For sequence of integers $c_1, c_2, \ldots, c_n$ the disorder of a sequence is equal to the length of the longest strictly increasing subsequence. Formally it is the largest integer $s$, such that there is an increasing sequence of indices $i_1 < i_2 < \ldots < i_s$ fulfilling $c_{i_1} < c_{i_2} < \ldots < c_{i_s}$.

Jurek thinks that his concerns are irrational if disorder of a sequence is at least $k$ -- then he is not interested in exact value of disorder. Problem is that it often turns out that some gold boxes from delivery are stolen or sometimes few gold boxes arrive with huge delay, so values of deliveries can change. You task is to calculate value of disorder after each change, or write $k$ if disorder is at least $k$.

In the first line one integer $Z \le 10$ is given, denoting number of testcases described in following lines. 

The first line contains two integers $n, k$, denoting number of deliveries and value of parameter $k$. The following line contains $n$ integers $c_1, c_2, \ldots, c_n$, denoting initial values of the deliveries. The third line contains one integer $q$, denoting number of times delivery values change. Following $q$ lines contains two integers $p_j, v_j$, denoting that $c_{p_j} = v_j$.

You should output $q$ lines, each containing one natural number. If disorder value after $j$-th change equals $s$, then you should write $\min (s, k)$ in $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]$