P12262 『STA - R9』Interleaving.

A sequence $p$ of length $m$ is called an interleaving sequence if and only if it has the form ${x,y,x,y,\cdots}$ and $x\ne y$. You are given a sequence $a_{1\dots n}$ of length $n$ and $q$ modifications. In each modification, two positive integers $k$ and $c$ are given, and $a_{k}=c$ is set. You need to find the length of the longest interleaving subsequence of $a$ initially (i.e., before the first modification) and after each modification.

The first line contains a positive integer $n$. The second line contains $n$ positive integers, denoting $a$. The third line contains a non-negative integer $q$. The next $q$ lines each contain two positive integers $k,c$, denoting one modification.

Output $q+1$ lines. The first line is the length of the longest interleaving subsequence of $a$ initially. The next $q$ lines: the $i$-th line is the length of the longest interleaving subsequence of $a$ after the $i$-th modification.

**This problem uses bundled testdata**, and the subtasks are as follows: | Subtask ID | $n\le $ | $q\le $ | Special Property | Score | | :----------: | :----------: | :----------: | :----------: | :----------: | | **0** | $1$ | $0$ | None | $2$ | | **1** | $20$ | $0$ | None | $5$ | | **2** | $3000$ | $7000$ | $a_{i},c\le 2$ | $23$ | | **3** | $250$ | $0$ | None | $10$ | | **4** | $1000$ | $0$ | None | $10$ | | **5** | $2000$ | $0$ | None | $10$ | | **6** | $3000$ | $0$ | None | $15$ | | **7** | $3000$ | $7000$ | None | $25$ | For $100\%$ of the data, it is guaranteed that $1\le n\le 3000$, $0\le q\le 7000$, and $1\le a_{i},k,c\le n$. Translated by ChatGPT 5