Two Kilers

폴란드 영화 Two Kilers의 주인공 Jurek Kiler는 금 상자 배송을 정기적으로 받는다. $i$번째 배송의 값은 그 안에 든 금 상자 가치의 합인 $c_i$이다.

최근 Jurek은 배송 값이 떨어지고 있다는 점이 걱정되었다. 이를 확인하려고 그는 배송 수열에 대한 척도를 정의했고, 이를 수열의 disorder라고 부른다. 정수열 $c_1, c_2, \ldots, c_n$의 disorder는 가장 긴 狭義 증가 부분 수열의 길이이다. 형식적으로는 $c_{i_1} < c_{i_2} < \ldots < c_{i_s}$이고 $i_1 < i_2 < \ldots < i_s$를 만족하는 수열이 존재하는 가장 큰 정수 $s$이다.

Disorder가 $k$ 이상이면 Jurek의 걱정은 근거가 없다고 보고, 정확한 값에는 관심이 없다. 금 상자 일부는 도난당하고, 일부는 큰 묶음으로 늦게 도착하므로 배송 값은 바뀔 수 있다. 값이 바뀔 때마다 disorder를 계산하되, disorder가 $k$ 이상이면 $k$를 출력한다.

첫 줄에 테스트 케이스의 수 $Z \le 10$이 주어진다.

각 테스트 케이스의 첫 줄에는 배송 수 $n$과 파라미터 $k$가 주어진다. 다음 줄에는 초기 배송 값 $c_1, c_2, \ldots, c_n$이 주어진다. 그다음 줄에는 값이 바뀌는 횟수 $q$가 주어진다. 이어지는 $q$개의 줄에는 $p_j$와 $v_j$가 주어지며, 이는 $c_{p_j} = v_j$로 바꾼다는 뜻이다.

각 테스트 케이스마다 $q$줄을 출력한다. 각 줄에는 자연수 하나를 적는다. $j$번째 변경 후 disorder가 $s$이면, $j$번째 줄에 $\min(s, k)$를 출력한다.

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

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

$p_j \in [1, n]$

$k \in [1, 20]$