-->

## Chef Likes Good Sequences Codechef October Lunchtime Problem solution -

Lets read the problem statement carefully.
Problem statement-

Chef calls a sequence good if it does not contain any two adjacent identical elements.

Initially, Chef has a sequence ${a}_{1},{a}_{2},\dots ,{a}_{N}$. He likes to change the sequence every now and then. You should process $Q$ queries. In each query, Chef chooses an index $x$ and changes the $x$-th element of the sequence to $y$. After each query, can you find the length of the longest good subsequence of the current sequence?

Note that the queries are not independent.

### Input

• The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
• The first line of each test case contains two space-separated integers $N$ and $Q$.
• The second line contains $N$ space-separated integers ${a}_{1},{a}_{2},\dots ,{a}_{N}$.
• $Q$ lines follow. Each of these lines contains two space-separated integers $x$ and $y$ describing a query.

### Output

After each query, print a single line containing one integer ― the length of the longest good subsequence.

### Constraints

• $1\le T\le 5$
• $1\le N,Q\le {10}^{5}$
• $1\le {a}_{i}\le {10}^{9}$ for each valid $i$
• $1\le x\le N$
• $1\le y\le {10}^{9}$

Subtask #1 (35 points): $Q=1$

Subtask #2 (65 points): original constraints

### Example Input

1
5 2
1 1 2 5 2
1 3
4 2


### Example Output

5
3

### Solution-

First of all do not confuse with subarray and subsequence.
A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. A subarray will always be contiguous but a subsequence need not be contiguous.

It's easy problem follow some simply step-
step 1- Calculate the longest subsequence in the initial array without changes.

Now think that if you made changes at xth position of array it will affect initial length if y!= a[x]
if y!=a[x] there occur some cases  for which initial length may affect. You have to observe these cases and handle initial length accordingly.

• Case 1 : ($a_x == a_{x-1}$) and ($a_x == a_{x+1}$), then answer will increase by $2$ as it will make $1$ segment into $3$ segments.
• Case 2 : ($a_x \neq a_{x-1}$) and ($a_x == a_{x+1}$), then the answer will increase by $1$ as earlier $a_x == a_{x+1}$ and $y$ will introduce an extra segment. If $y$ $=$ $a_{x-1}$ then we will reduce the answer by $1$ as earlier we added $1$ as changing to $y$ increased the segment count but now it will be merged with previous segment. Example : let $a_x = a_{x+1} = 1$ and $a_{x-1} = 2$, so If $y$ $=$ $3$ answer will increase by $1$, and if $y = 2$ then there will no change to the answer.
• Case 3 : ($a_x == a_{x-1}$) and ($a_x \neq a_{x+1}$), similar to above case, we will increase the answer by $1$. if $y=a_{x+1}$ then we will reduce the answer by $1$.
• Case 4 : ($a_x \neq a_{x-1}$) and ($a_x \neq a_{x+1}$), then if $y=a_{x-1}$ we will reduce answer by $1$. if $y = a_{x+1}$ we will reduce answer by $1$.(Note that you might reduce the answer by $2$ when $y=a_{x-1}=a_{x+1}$).

Must join my telegram channel -https://t.me/competitiveProgrammingDiscussion

Follow my code -