A Unique Array
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 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.
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 105
- 1 ≤ q ≤ 105
- 0 ≤ x < Size of Array A
- 1 ≤ y ≤ 109
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.
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]