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

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

Initially, Chef has a sequence . He likes to change the sequence every now and then. You should process queries. In each query, Chef chooses an index and changes the -th element of the sequence to . 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 denoting the number of test cases. The description of test cases follows.
- The first line of each test case contains two space-separated integers and .
- The second line contains space-separated integers .
- lines follow. Each of these lines contains two space-separated integers and describing a query.

### Output

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

### Constraints

- for each valid

### Subtasks

Subtask #1 (35 points):

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.

- 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}$).

## Comments

## Post a Comment