题目描述

一个序列 $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$。