103813: [Atcoder]ABC381 D - 1122 Substring

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.

问题陈述

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

• $\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 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序列的条件。