F - 1122 Subsequence Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 525

問題文

正整数からなる(空でも良い)数列 X=(X_1,X_2,\ldots) が以下の 3 つの条件をすべてみたすとき、かつそのときに限り、X1122 数列 と呼びます。
(1122 数列の定義はD問題と共通です。)

  • \lvert X \rvert は偶数である。ここで、\lvert X \rvertX の長さを表す。
  • 1\leq i\leq \frac{\lvert X \rvert}{2} をみたす整数 i について、X_{2i-1}X_{2i} は等しい。
  • 各正整数は X に現れないか、ちょうど 2 回現れるかのどちらかである。すなわち、X に含まれる正整数は X にちょうど 2 回ずつ登場する。

正整数からなる長さ 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,4,5,6 項目をとると (1,1,2,2) となりますが、これは長さが 4 の 1122 数列となっています。
これより長い部分列であって、1122 数列の条件をみたすようなものは存在しないため、4 を出力します。


入力例 2

1
20

出力例 2

0

Score : 525 points

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