解法 \(1\) : 連続部分列のうち、\(A\) の奇数項目から始まるものと偶数項目から始まるものについて分けて考える解法

以下では、\(A\) の奇数項目 \(A_1, A_3,\ldots\) のいずれかから始まるような連続部分列であって、 1122 数列であるようなもののうち最長なものの長さをもとめる手法について解説します。これが求められれば、偶数項目から始まるような連続部分列についても同様に計算でき、そのうち大きい方の値を出力すれば良いです。

ここで、大事なことは次の事実です。

• \(1\leq l<r\leq N\) について、\((A_l,A_{l+1},\ldots,A_{r})\) が1122数列であるとき、最後から \(2\) 項取り除いた列、すなわち \((A_l,A_{l+1},\ldots,A_{r-2})\) も1122数列である。ここで、\(r-l=2\) のときは取り除いた後の数列は空列となることに注意する。

このことから尺取り法を用いてこの問題を解くことができます。

まず、偶数 \(r=2,4,\ldots\) に対して、\((A_l,A_{l+1},\ldots,A_r)\) が1122数列となる最小の奇数 \(l\) \((1\leq l\leq r+1)\) を \(f(r)\) として定義します。ここで、\(l=r+1\) のときは \((A_l,A_{l+1},\ldots,A_r)\) は空列となり、特に1122数列となることから、このような \(f(r)\) は必ず定義されます。
さらにこのとき、上の事実から、 \(f(r)\) が広義単調増加となることがわかります。

求めたい値、すなわち「 \(A\) の奇数項目 \(A_1, A_3,\ldots\) のいずれかから始まるような連続部分列であって、 1122 数列であるようなもののうち最長なものの長さ」は、\(f(r)\) を用いて \(\displaystyle \max_{r=2,4,\ldots} (r-f(r)+1)\) と表されます。

さて、\(f(r)\) を \(r=2,4,\ldots\) に対して順に求めていくことを考えます。
\(r=2\) のときは、\(A_1=A_2\) ならば \(l=1\), そうでないならば \(l=3\) です。
\(f(r-2)\) が求まっているとき、\(f(r)\) は次のようにして求められます。

1. \(A_{r-1}\neq A_r\) ならば、\(f(r)=r+1\) となる。
2. \(A_{r-1}=A_r\) のとき、\(A_{f(r-2)}, A_{f(r-2)+2}, \ldots, A_{r-3}\) の中に \(A_{r-1}\) と一致するものがなければ、\(f(r)=f(r-2)\) となる。
3. \(A_{r-1}=A_r\) かつ \(A_{r-1}=A_k\) となる \(k\in \{ f(r-2), f(r-2)+2,\ldots, r-3\}\) が存在するとき、\(f(r)=k+2\)となる。ここで、\((A_{f(r-2)},A_{f(r-2)+1},\ldots,A_{r-2})\) が1122数列であることからそのような \(k\) は存在するならば一意であることに注意する。

さて、\(A_{f(r-2)}, A_{f(r-2)+2}, \ldots, A_{r-3}\) の中に \(A_{r-1}\) と一致するものが存在するか、存在するならばどれかを求める方法について愚直に実装すると最悪ケースで \(\Theta(r)\) の計算量がかかり、全体の計算量が \(\Theta(N^2)\) となるため間に合いません。
そのため、この計算を高速に行う必要があります。方法はいくつか考えられますが、例えば、制約から \(A_i\leq N\) \((\leq 2\times 10^5)\) が成り立つことから、各 \(1\leq x\leq N\) について \(i=1,3,\ldots, r-3\) の中で \(A_i=x\) となる最大の \(i\) （存在しないならば \(-1\) ）を記録しておき、\(A_i=A_{r-1}\) となる最大の \(i\) が \(f(r-2)\) 以上であるか、あるならばその値は何かを使うことで \(O(1)\) で求めることができます。この記録自体についても、各 \(r\) において 1ヶ所のみを更新（\(x=A_{r-1}\) について \(f(i)=x\) となる最大の \(i\) を \((r-1)\) へ更新）すれば良く、全体で \(O(N)\) の計算量しかかかりません。よって、このようにすると全体で \(O(N)\) の計算量で問題を解くことができます。

よって、この問題を十分高速に解くことができました。
なお、C++ の std::map などのデータ構造を使うことで \(O(N\log N)\) で解くこともできます。

解法 \(2\) : 1122数列の定義を奇数項の場合にまで一般化し、まとめて解く解法

1122数列 を奇数項の列まで一般化したものとして、良い列 を次の条件をみたす列 \(X=(X_1,X_2,\ldots)\) として定義します。

• \(1\leq i\leq \lfloor \frac{\lvert X \rvert}{2}\rfloor \) をみたす整数 \(i\) について、\(X_{2i-1}\) と \(X_{2i}\) は等しい。
• \(X\) の奇数項目 \(X_1,X_3,\ldots, X_{ 2\cdot\lfloor \frac{\lvert X \rvert+1}{2}\rfloor -1}\) はすべて異なる。

ここで、\(X\) は良い列かつ偶数項からなるとき、かつそのときに限り1122数列となることに注意してください。
また、良い列は次の性質を持ちます。

• 良い列の最後尾から何項かを取り除いたものもまた良い列となる。

これらのことから、\((A_1,A_2,\ldots, A_N)\) の連続部分列であって良い列であるようなものとしてあり得る最長のものの長さが \(M\) であるとき、答えは \(M\) 以下の最大の偶数 \((=2\cdot \lfloor \frac{M}{2}\rfloor)\) となります。また、この性質を用いて尺取り法によってこの問題を解くことができます。

以下は、解法1とほぼ同様の方法です。
\(1\leq r\leq N\) に対して、\((A_l,A_{l+1},\ldots,A_r)\) が良い列となる最小の \(l\) \((1\leq l\leq r)\) を \(g(r)\) として定義します。ここで、\(l=r\) のときは \((A_l,A_{l+1},\ldots,A_r)\) は \(1\) つの項のみからなる列となり、特に良い列となることから、このような \(g(r)\) は必ず定義されます。
\((A_1,A_2,\ldots, A_N)\) の連続部分列であって良い列であるようなものとしてあり得る最長のものの長さ \(M\) は、\(g(r)\) を用いて \(M=\displaystyle \max_{1\leq r\leq N} (r-g(r)+1)\) で表されます。
さらにこのとき、上の性質から、\(g(r)\) が広義単調増加となることがわかります。

\(g(r)\) を \(r=1,2,\ldots\) に対して順に求めていくことを考えます。
つねに \(g(1)=1\) です。 \(g(r-1)\) が求まっているとき、\(g(r)\) は次のようにして求められます。

• \((r-g(r-1))\) が偶数のとき

1. \(A_{g(r-1)}, A_{g(r-1)+1}, \ldots, A_{r-1}\) の中に \(A_r\) と一致するものがなければ、\(g(r)=g(r-1)\) となる。
2. \(A_{r}=A_k\) となる \(k\in \{ g(r-1), g(r-1)+1,\ldots, r-1\}\) が存在するとき、そのようなもののうち最大の \(k\) を \(k_0\) として、\(k_0=r-1\) ならば \(g(r)=k_0\) となる。そうでないならば、\(g(r)=k_0+1\) となる。

• \((r-g(r-1))\) が奇数のとき

1. \(A_{r-1}=A_r\) ならば \(g(r)=g(r-1)\) となる。
2. \(A_{r-1}\neq A_r\) ならば \(g(r)=r\) となる。

この定め方の正当性の証明については場合分けが必要ですが、それぞれは定義からすぐに従うためここでは省略します。
\(g(r)\) の値を各 \(r\) に対して \(O(1)\) で計算するためには、 各 \(1\leq x\leq N\) について \(i=1,2,\ldots, r-1\) の中で \(A_i=x\) となる最大の \(i\) （存在しないならば \(-1\) ）を記録しておけばよいです。 この方法によって、全体で \(O(N)\) の計算量でこの問題を解くことができます。

よって、この問題を十分高速に解くことができました。

c++ による実装例（解法 \(1\)）:

#include <bits/stdc++.h>
using namespace std;

#define rep(i, n) for(int i = 0; i < n; ++i)
#define N 200000

int main() {
	int n,l,ans=0;
	int a[N];
	int last[N+1];
	cin>>n;
	rep(i,n)cin>>a[i];

	rep(i,N)last[i+1]=-2;
	l=0;
	for(int i=0;(i+1)<n;i+=2){
		if(a[i]!=a[i+1])l=i+2;
		else l=max(l,last[a[i]]+2);
		ans=max(ans,i+2-l);
		last[a[i]]=i;
	}

	rep(i,N)last[i+1]=-2;
	l=1;
	for(int i=1;(i+1)<n;i+=2){
		if(a[i]!=a[i+1])l=i+2;
		else l=max(l,last[a[i]]+2);
		ans=max(ans,i+2-l);
		last[a[i]]=i;
	}
	cout<<ans<<endl;
	return 0;
}

c++ による実装例（解法 \(2\)）:

#include <bits/stdc++.h>
using namespace std;

#define rep(i, n) for(int i = 0; i < n; ++i)
#define N 200000

int main() {
	int n,l,ans=0;
	int a[N];
	int last[N+1];
	cin>>n;
	rep(i,n)cin>>a[i];

	rep(i,N)last[i+1]=-2;
	l=0;
	rep(i,n){
		if((i-l)%2==0){
			if(last[a[i]]==i-1)l=last[a[i]];
			else if(last[a[i]]>=l)l=last[a[i]]+1;			
		}
		else{
			if(a[i-1]!=a[i])l=i;
		}
		ans=max(ans,i-l+1);
		last[a[i]]=i;
	}
	cout<<(2*(ans/2))<<endl;
	return 0;
}