103815: [Atcoder]ABC381 F - 1122 Subsequence

Problem Statement

A sequence $X = (X_1, X_2, \ldots)$ of positive integers (possibly empty) is called a 1122 sequence if and only if it satisfies all of the following three conditions: (The definition of a 1122 sequence is the same as in Problem D.)

• $\lvert X \rvert$ is even. Here, $\lvert X \rvert$ denotes the length of $X$.
• For each integer $i$ satisfying $1\leq i\leq \frac{|X|}{2}$, $X_{2i-1}$ and $X_{2i}$ are equal.
• Each positive integer appears in $X$ either not at all or exactly twice. That is, every positive integer contained in $X$ appears exactly twice in $X$.

Given a sequence $A = (A_1, A_2, \ldots, A_N)$ of length $N$ consisting of positive integers, print the maximum length of a subsequence (not necessarily contiguous) of $A$ that is a 1122 sequence.

Constraints

• $1\leq N \leq 2 \times 10^5$
• $1\leq A_i \leq 20$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$
$A_1$ $A_2$ $\ldots$ $A_N$

Output

Print the maximum length of a (not necessarily contiguous) subsequence of $A$ that is a 1122 sequence.

Sample Input 1

7
1 3 3 1 2 2 1

Sample Output 1

4

For example, choosing the $1$-st, $4$-th, $5$-th, and $6$-th elements of $A$, we get $(1, 1, 2, 2)$, which is a 1122 sequence of length $4$.
There is no longer subsequence that satisfies the conditions for a 1122 sequence, so the answer is $4$.

Sample Input 2

1
20

Sample Output 2

0

问题陈述

一个由正整数（可能为空）组成的序列 $X = (X_1, X_2, \ldots)$ 被称为1122序列，当且仅当它满足以下三个条件：（1122序列的定义与问题D中的相同。）

• $\lvert X \rvert$ 是偶数。这里，$\lvert X \rvert$ 表示 $X$ 的长度。
• 对于每个满足 $1\leq i\leq \frac{|X|}{2}$ 的整数 $i$，$X_{2i-1}$ 和 $X_{2i}$ 相等。
• 每个正整数在 $X$ 中要么不出现，要么恰好出现两次。即，包含在 $X$ 中的每个正整数在 $X$ 中恰好出现两次。

给定一个由正整数组成的长度为 $N$ 的序列 $A = (A_1, A_2, \ldots, A_N)$，打印 $A$ 的一个子序列（不一定是连续的）的最大长度，该子序列是1122序列。

约束条件

• $1\leq N \leq 2 \times 10^5$
• $1\leq A_i \leq 20$
• 所有输入值都是整数。

输入

输入从标准输入以下格式给出：

$N$
$A_1$ $A_2$ $\ldots$ $A_N$

输出

打印 $A$ 的一个（不一定是连续的）子序列的最大长度，该子序列是1122序列。

样本输入 1

7
1 3 3 1 2 2 1

样本输出 1

4

例如，选择 $A$ 的第 $1$-st、$4$-th、$5$-th 和 $6$-th 元素，我们得到 $(1, 1, 2, 2)$，这是一个长度为 $4$ 的1122序列。
没有更长的子序列满足1122序列的条件，所以答案是 $4$。

样本输入 2

1
20

样本输出 2

0