Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

A Unique Array

Limits: 2s, 512 MB

An array is called “unique” if it has no consecutive element with same value(A[i] != A[i-1]).

Given a unique array A of N integer and q queries. Each query will contain 2 integer x,y which updates the value of index x to y (A[x] = y). After each query, if the array is not unique, delete some elements from A to make it unique. Output the maximum size of A which is unique.

Input

Input starts with an integer T, denoting the number of test cases. The next line contains two integers N, q . The next line contains N space separated integers forming the array A.

The next q lines will contain a query which is in the form x y.

Constraints:

  • 1 ≤ T ≤ 10
  • 1 ≤ N ≤ 105
  • 1 ≤ q ≤ 105
  • 0 ≤ x < Size of Array A
  • 1 ≤ y ≤ 109

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 A which is unique.

Samples

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

For testcase 1

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

To make it unique, we remove the first element from A making A = [2,3,4,5]

After second operation, A = [2,3,4,3] , It is unique, so no delete operation needed

After third opeation, A = [2,3,3,3], The largest unique array A = [2,3]

Discussion