Problem Description

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.

Input Format

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 Format

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.

5
2 3 1 3 3 
1
2 3

3
3

Hint

This problem uses bundled testdata, and the subtasks are as follows:

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