Description

称一个长度为 $m$ 的序列 $p$ 为交错序列，当且仅当其具有 ${x,y,x,y,\cdots}$ 的形式，且 $x\ne y$。

给定一个长度为 $n$ 的序列 $a_{1\dots n}$ 和 $q$ 次修改，每次修改会给定两个正整数 $k$ 和 $c$，并令 $a_{k}=c$。你需要在初始时（即第一次修改前）以及每次修改之后求出 $a$ 的最长的交错子序列的长度。

Input Format

第一行一个正整数 $n$。

第二行 $n$ 个正整数，表示 $a$。

第三行一个非负整数 $q$。

接下来 $q$ 行，每行两个正整数 $k,c$，表示一次修改。

Output Format

输出 $q+1$ 行。

第一行表示初始时 $a$ 的最长的交错子序列的长度。

接下来 $q$ 行，第 $i$ 行表示第 $i$ 次修改后 $a$ 的最长的交错子序列的长度。

5
2 3 1 3 3 
1
2 3

3
3

Hint

本题使用捆绑测试，子任务信息如下：

对于 $100\%$ 的数据，保证 $1\le n\le 3000$，$0\le q\le 7000$，$1\le a_{i},k,c\le n$。