配对序列

一个序列 $s_1,\ldots s_{2k}$ 是**配对的**，当且仅当： - 对于任意 $1\le i \le k$，$s_{2i}=s_{2i-1}$。 - 对于任意 $1\le i<k$，$s_{2i}\ne s_{2i+1}$。 注意，配对的序列长度必然为偶数。 例如，$3,3,5,5,2,2$ 是配对的，而 $2,2,2,2,5,5$（$s_2=s_3$ 不满足第二条要求）或者 $1,2,3,3,1,1$（$s_1\ne s_2$ 不满足第一条要求）都不是配对的。 给出一个数列 $a_1,\ldots, a_n$，求所有配对的子序列长度的最大值。

输入的第一行有一个正整数 $n$，表示序列的长度。 第二行有 $n$ 个正整数 $a_1,\ldots,a_n$，表示这个序列。

输出一行一个自然数，表示最长的配对子序列长度。特别地，如果不存在非空的配对子序列，那么输出 $0$。

8
1 2 2 2 2 1 2 2

4

11
1 1 4 1 1 2 1000 2 5 5 4

6

参见 pairing3.in

参见 pairing3.out

参见 pairing4.in

参见 pairing4.out

【样例 1 解释】 取 $1,1,2,2$ 这个子序列即可。 【样例 2 解释】 取 $1,1,2,2,5,5$ 这个配对子序列即可。 【样例 3 解释】 该样例符合测试点 $3$ 的限制。 【样例 4 解释】 该样例符合测试点 $12$ 的限制。 【数据范围】 对于全体数据，保证 $2\le n\le 5\times 10^5$，$1\le a_i\le 5\times 10^5$。 |测试点编号|$n\le$|$a_i\le$|特殊性质| |:-:|:-:|:-:|:-:| |$1\sim 2$|$18$|$5\times 10^5$|| |$3\sim 5$|$500$|$500$|| |$6\sim 7$|$5000$|$5000$|| |$8\sim 9$|$5000$|$5\times 10^5$|| |$10$|$5\times 10^5$|$5\times 10^5$|每个数最多出现 $1$ 次| |$11$|$5\times 10^5$|$5\times 10^5$|$a_i\le a_{i+1}$ 恒成立| |$12\sim 14$|$5\times 10^5$|$5\times 10^5$|每个数最多出现 $2$ 次| |$15\sim 20$|$5\times 10^5$|$5\times 10^5$||