该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

配对序列

题目描述

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

输入输出样例 #1

输入 #1

8
1 2 2 2 2 1 2 2

输出 #1

4

输入输出样例 #2

输入 #2

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

输出 #2

6

输入输出样例 #3

输入 #3

参见 pairing3.in

输出 #3

参见 pairing3.out

输入输出样例 #4

输入 #4

参见 pairing4.in

输出 #4

参见 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$。