Problem Description

In the AtCoder Kingdom, the tallest tower, "AtCoder Tower," has $ N $ ornaments arranged in a straight line for Christmas.

There are $ N $ types of colors for the ornaments, numbered as color $ 1 $, color $ 2 $, color $ 3 $, ..., color $ N $. Initially, the $ i $-th ornament from the left in "AtCoder Tower" is color $ A_i $.

Now, Takahashi, the king, wants to make the decoration look "good" by removing some of the ornaments. A "good" state is defined as meeting all the following conditions:

• The number of remaining ornament colors is at most $ 2 $.
• No two adjacent ornaments have the same color.

For example, if you remove ornaments like \[A\] \[B\], it results in a "good" state.

On the other hand, if you remove ornaments like \[C\] \[D\], it does not result in a "good" state.

In "AtCoder Tower," the Christmas decoration is done over $ Q+1 $ days. On the night of the $ i $-th day, the color of the $ X_i $-th ornament from the left is changed to color $ Y_i $.

For each $ i = 1, 2, ..., Q+1 $, determine the following:

• If Takahashi wants to make the decoration look "good" at the beginning of the $ i $-th day, what is the minimum number of ornaments that need to be removed?

Input Format

The input is given from the standard input in the following format:

$ N $ $ A_1 $ $ A_2 $ $ A_3 $ ... $ A_N $ $ Q $ $ X_1 $ $ Y_1 $ $ X_2 $ $ Y_2 $ $ X_3 $ $ Y_3 $ : $ X_Q $ $ Y_Q $

Output Format

Output $ Q+1 $ lines. The $ i $-th line should contain the minimum number of ornaments that need to be removed to make the decoration look "good" at the beginning of the $ i $-th day.

Sample Input and Output

Sample Input #1

1
1
0

Sample Output #1

0

Sample Input #2

10
1 3 4 2 3 1 4 2 1 4
0

Sample Output #2

4

Sample Input #3

12
8 9 9 4 4 11 11 8 4 9 9 4
10
3 9
1 4
2 9
10 11
7 4
1 8
3 8
6 9
6 8
2 9

Sample Output #3

8
8
7
7
7
7
7
7
6
6
6

Notes/Hints

Constraints

• $1 \leq N \leq 3,000$
• $0 \leq Q \leq 7,000$
• $1 \leq X_i \leq N$
• $1 \leq Y_i \leq N$
• $1 \leq A_i \leq N$
• All inputs are integers.

Partial Points

This problem is divided into several sub-tasks. Your score is the sum of the points for the sub-tasks you solve correctly.

1. (2 points) $ N = 1 $, $ Q = 0 $.
2. (11 points) $N \leq 15$, $ Q = 0 $.
3. (12 points) $A_i \leq 2$, $Y_i \leq 2$.
4. (13 points) $N \leq 250$, $ Q = 0 $.
5. (18 points) $ Q = 0 $.
6. (44 points) No additional constraints.

For sub-task 6, scoring is as follows:

• Correct on all test cases where $Q \leq 600$ to get 24 points.
• Correct on all test cases where $Q \leq 1,500$ to get an additional 5 points.
• Correct on all test cases where $Q \leq 2,500$ to get an additional 5 points.
• Correct on all test cases where $Q \leq 4,500$ to get an additional 5 points.
• Correct on all test cases to get an additional 5 points.

Hint for Sub-task 3

In this sub-task, the color of the ornaments is either color $ 1 $ or color $ 2 $ for any day. This means that the "good" state can only be achieved by alternating colors $ 1, 2, 1, ... $ or $ 2, 1, 2, ... $ from left to right. Consider this hint when tackling sub-task 3.

Sample Explanation 1

In this input example, the decoration is already in a "good" state without removing any ornaments. Therefore, the correct output is $ 0 $.

Sample Explanation 2

As shown in the figure below, removing 4 ornaments results in a "good" state.

This input example satisfies the constraints of sub-task 2.

Sample Explanation 3

Since $ Q = 10 $, you need to output 11 lines.

见题面 Input 部分

见题面 Output 部分