Limits 2s, 512 MB

An array is called "unique" if it has no consecutive element with same value(A[i] != A[i-1]\text{A[i] != A[i-1]}).

Given a unique array AA of NN integer and qq queries. Each query will contain 2 integer xx, yy which updates the value of index xx to yy (A[x] = y\text{A[x] = y}). After each query, if the array is not unique, delete some elements from AA to make it unique. Output the maximum size of AA which is unique.

Input

Input starts with an integer TT (1T101 ≤ T ≤ 10), denoting the number of test cases. The next line contains two integers N (1N1051 ≤ N ≤ 10^5), q (1q1051 ≤ q ≤ 10^5).

The next line contains NN space separated integers forming the array AA.

The next qq lines will contain a query which is in the form x y\text{x y} (0x<A0 ≤ x < |A|, 1y1091 ≤ y ≤ 10^9).

Output

For each test case, print the case number in a single line. Then for each query you have to print a line containing the output: the maximum size of AA which is unique.

Sample

InputOutput
2
5 3
1 2 3 4 5
0 2
3 3
2 3
1 1
10
0 4
Case 1:
4
4
2
Case 2:
1

In the case of test case 1:

A=[1,2,3,4,5]A = [1, 2, 3, 4, 5]

After the first operation A=[2,2,3,4,5]A = [2, 2, 3, 4, 5],

To make it unique, we remove the first element from AA making A=[2,3,4,5]A = [2,3,4,5]. After the second operation, A=[2,3,4,3]A = [2,3,4,3], it is unique, so no delete operation needed.

After third operation A=[2,3,3,3]A = [2, 3, 3, 3], the largest unique array A=[2,3]A = [2, 3].


Submit

Login to submit.

Contributors

Statistics

75% Solution Ratio
IstiaqueShubhoEarliest, Feb '19
reaziiiFastest, 0.0s
masud_ali58Lightest, 8.0 kB
mdvirusShortest, 635B
Toph uses cookies. By continuing you agree to our Cookie Policy.