/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 425 点
問題文
正整数からなる（空でも良い）数列 X=(X_1,X_2,\ldots) が以下の 3 つの条件をすべてみたすとき、かつそのときに限り、X を 1122 数列 と呼びます。
（1122 数列の定義はF問題と共通です。）
- \lvert X \rvert は偶数である。ここで、\lvert X \rvert は X の長さを表す。
- 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 N
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \ldots A_N
出力
A の連続する部分列であって、1122 数列であるようなもののうち最長のものの長さを出力せよ。
入力例 1
8 2 3 1 1 2 2 1 1
出力例 1
4
例えば A の 3 項目から 6 項目までの連続部分列をとると (1,1,2,2) となりますが、これは長さが 4 の 1122 数列となっています。
これより長い部分列であって、1122 数列の条件をみたすようなものは存在しないため、4 を出力します。
入力例 2
3 1 2 2
出力例 2
2
入力例 3
1 1
出力例 3
0
項数が 0 の列も 1122 数列の条件をみたしていることに注意してください。
Score : 425 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 F.)
- \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 (contiguous) subarray of A that is a 1122 sequence.
Constraints
- 1\leq N \leq 2 \times 10^5
- 1\leq A_i \leq N
- 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 (contiguous) subarray of A that is a 1122 sequence.
Sample Input 1
8 2 3 1 1 2 2 1 1
Sample Output 1
4
For example, taking the subarray from the 3-rd to 6-th elements of A, we get (1, 1, 2, 2), which is a 1122 sequence of length 4.
There is no longer (contiguous) subarray that satisfies the conditions for a 1122 sequence, so the answer is 4.
Sample Input 2
3 1 2 2
Sample Output 2
2
Sample Input 3
1 1
Sample Output 3
0
Note that a sequence of length 0 also satisfies the conditions for a 1122 sequence.