操作によって、\(A\) に含まれる各整数の個数は変わらないため、操作の繰り返しによって \(A\) が広義単調増加になった時の状態は \(A\) をソートしたものとして一意に定まります。これを \(B=(B_1,B_2,\ldots,B_N)\) とします。
さらに、\(C_{i,j}\) \((1\leq i,j\leq 4)\)を\(1\leq k\leq N\) をみたす整数であって、\(A_k=i\) かつ \(B_k=j\) をみたすものの個数として定義します。
ここで、\((1,2,3,4)\) の順列 \(p=(p_1,p_2,p_3,p_4)\) に対して、

\[ f(p)=\sum_{i=1}^4\sum_{j=i+1}^{4} C_{p_i,p_j} \]

という量を考えます。ここで、\(f(p)\) が \(1\) 回の操作で高々 \(1\) しか減少しない事を示します。 \(A_i=p_w\), \(B_i=p_x\), \(A_j=p_y\), \(B_j=p_z\) であるような\((i,j)\) を選んで操作を行ったとします。 このとき、\(C_{p_w,p_x}\) と \(C_{p_y,p_z}\) が \(1\) 減少し、 \(C_{p_y,p_x}\), \(C_{p_w,p_z}\) が \(1\) 増加します。 \(f(p)\) は高々 \(2\) しか減少せず、\(C_{p_w,p_x}\) と \(C_{p_y,p_z}\) がともに減少するためには \(w<x\) かつ \(y<z\) でなくてはなりません。しかし、このとき、\(w\leq y\) ならば \(w<z\), \(w>y\) ならば \(y<x\) となり、全体で高々 \(1\) しか減少しない事がわかります。 よって、少なくとも

\[ \max_p \left(\sum_{i=1}^4\sum_{j=i+1}^{4} C_{p_i,p_j} \right) \]

回の操作が必要です。ここで、\(\max\) の添字 \(p\) は \((1,2,3,4)\) の順列全体を動くものとします。

次に、この回数の操作を行えば、広義単調増加とできる事を示します。まず、各\(i\neq j\) について、 \(A_k=i\) かつ \(B_k=j\) 、\(A_{k'}=j\) かつ \(B_{k'}=i\) であるような \(k,k'\) が存在する限り選んで操作を行うという事を繰り返します。 この操作は \(C_{i,j}\), \(C_{j,i}\) をちょうど \(1\) 減少させ、 \(C_{i,i}\), \(C_{j,j}\) をちょうど \(1\) 増加させるため、上で述べた \(f(p)\) の値を（\(p\) によらず）ちょうど \(1\) 減少させます。

この操作が行えなくなった時点で、\(i\neq j\)について、\(C_{i,j}\) と \(C_{j,i}\) の少なくとも一方は \(0\) となっています。さて、ここで 頂点が \(1\) から \(4\) まで番号づけられた \(4\) 頂点のグラフ \(G\) であって、この時点において、\(i\neq j\) について、\(C_{i,j}>0\) であるときかつその時に限り頂点. \(i\) から 頂点 \(j\) へ重み \(C_{i,j}\) の有向辺が張られているようなものを考えます。
まず、\(G\) の辺が\(6\) 本である (\(C_{i,j}=C_{j,i}=0\) となっているような \(i\neq j\) が存在しない)場合を考えます。この時、重さを一度無視すると、実はグラフは同型を除いて一意に定まります。すなわち、頂点の番号をうまく付け替える事で同じ形のグラフとなります。まず、これを示します。\(G\) は次の条件をみたします。

• 相異なるどの \(2\) 頂点の組についてもちょうど一方向のみに辺が伸びている。
• 各頂点の入次数, 出次数は \(1\) または \(2\)

後者は、\(A\) と \(B\) における 各数の個数が等しいことから、各 \(1\leq i\leq 4\) について \(\displaystyle\sum_{j=1}^4C_{i,j}=\displaystyle\sum_{j=1}^4C_{j,i}\) となることから、各頂点について、(頂点に向かう辺の重みの和)\(=\)(頂点から出る辺の重みの和)である必要がある\(\cdots(I)\)事から従います。

さて、この時、出次数が \(2\) の頂点はちょうど \(2\) つであり、これらを頂点 \(p_1,p_2\) とし、さらにこの \(2\) 点間で 頂点 \(p_1\) から頂点 \(p_2\) の方へ辺が伸びているように番号をつけます。一方で入次数が \(2\) の頂点のうち頂点 \(p_3\) から頂点 \(p_4\) の方へ辺が伸びているように番号をつけます。 このとき、辺は上の条件から

• 辺 \(1\): 頂点 \(p_1\) \(\to \) 頂点 \(p_3\)
• 辺 \(2\): 頂点 \(p_2\) \(\to \) 頂点 \(p_3\)
• 辺 \(3\): 頂点 \(p_2\) \(\to \) 頂点 \(p_4\)
• 辺 \(4\): 頂点 \(p_1\) \(\to \) 頂点 \(p_2\)
• 辺 \(5\): 頂点 \(p_3\) \(\to \) 頂点 \(p_4\)
• 辺\( 6\): 頂点 \(p_4\) \(\to \) 頂点 \(p_1\)

であると分かります。 さらに、辺 \(1,2,3\) の重みを \(W_1\), \(W_2\), \(W_3\)とすると、\((I)\)より辺 \(4,5,6\) の重みはそれぞれ \(W_2+W_3\), \(W_1+W_2\), \(W_1+W_2+W_3\) となります。このとき、次の操作を行う事ができます。

• \(A_{k_1}=p_1\) かつ \(B_{k_1}=p_3\), \(A_{k_2}=p_3\) かつ \(B_{k_2}=p_4\), \(A_{k_3}=p_4\) かつ \(B_{k_3}=p_1\) をみたす\((k_1,k_2,k_3)\) を選び、\((i,j)=(k_1,k_2), (k_2,k_3)\) として操作を行う。これを \(W_1\) 回繰り返す。

• \(A_{k_1}=p_2\) かつ \(B_{k_1}=p_3\), \(A_{k_2}=p_3\) かつ \(B_{k_2}=p_4\), \(A_{k_3}=p_4\) かつ \(B_{k_3}=p_1\), \(A_{k_4}=p_1\) かつ \(B_{k_4}=p_2\) をみたす\((k_1,k_2,k_3,k_4)\) を選び、\((i,j)=(k_1,k_2), (k_2,k_3), (k_3,k_4)\) として操作を行う。これを \(W_2\) 回繰り返す。

• \(A_{k_1}=p_2\) かつ \(B_{k_1}=p_4\), \(A_{k_2}=p_4\) かつ \(B_{k_2}=p_1\), \(A_{k_3}=p_1\) かつ \(B_{k_3}=p_2\) をみたす\((k_1,k_2,k_3)\) を選び、\((i,j)=(k_1,k_2), (k_2,k_3)\) として操作を行う。これを \(W_3\) 回繰り返す。

なお、これらのすべての操作にわたって、同じ添字は \(k_\alpha\) \((\alpha=1,2,3,4)\) として\(2\) 回以上選ばないようにします。 これらの操作ができることは \(G\) の定義から従い、その後で\(A\) は広義単調増加となります。このとき、グラフの頂点番号に対して定めた \((p_1,p_2,p_3,p_4)\) について、 \(\displaystyle\sum_{i=1}^4\displaystyle\sum_{j=i+1}^{4} C_{p_i,p_j} \) は毎回の操作でちょうど \(1\) ずつ減っていることから、 全体で操作回数は \(\displaystyle\sum_{i=1}^4\displaystyle\sum_{j=i+1}^{4} C_{p_i,p_j} \) であり、必要な最小の操作回数は

\[ \max_p \left(\sum_{i=1}^4\sum_{j=i+1}^{4} C_{p_i,p_j} \right) \]

回以下である事がわかります。 さて、\(G\) の辺が\(6\) 本でない場合のグラフの形としては同型でない場合を除いて \(5\) 本の場合に \(2\) 通り、 \(3,4\) 本の場合に各 \(1\) 通りありますが、いずれも上で考えた \(6\) 本の場合のグラフから適切に辺を取り除いた形であり、どちらの方向にも辺が伸びていない (相異なる) \(2\) 頂点間に適切な方向に重み \(0\) の辺を張る事で、\(W_1, W_2, W_3\) のうち \(1\) つ以上 を \(0\) としたものとして考える事ができます。よって、この場合も変わらず必要な操作の最小回数は\( \displaystyle\max_p \left(\sum_{i=1}^4\sum_{j=i+1}^{4} C_{p_i,p_j} \right) \)回以下とわかります。 これが先ほど求めた下限と一致していることから、答えは

\[ \displaystyle\max_p \left(\sum_{i=1}^4\sum_{j=i+1}^{4} C_{p_i,p_j} \right) \]

となります。 \(B\) を求めるのに \(O(N)\) (通常のソートアルゴリズムを使った場合は \(O(N\log N)\))、\(C\) を求めるのに \(O(N)\), 順列と総和記号の計算は\(O(1)\) (\(N\) によらず、 \(4!\times \frac{4\cdot 5}{2}=240\) 回程度) であるため全体で \(O(N)\) であり、十分高速にこの問題を解くことができました。

c++による実装例:

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

int main(void){
	vector<int>p;
	for(int i=0;i<4;i++)p.push_back(i);

	int n;
	cin>>n;

	vector<int>a(n),b;
	for(int i=0;i<n;i++)cin>>a[i];
	for(int j=1;j<=4;j++)for(int i=0;i<n;i++)if(a[i]==j)b.push_back(j);

	vector<vector<int> >c(4,vector<int>(4));
	for(int i=0;i<n;i++)c[a[i]-1][b[i]-1]++;

	int s,ans=0;
	while(true){
		s=0;
		for(int i=0;i<4;i++)for(int j=i+1;j<4;j++)s+=c[p[i]][p[j]];
		ans=max(ans,s);
		if(!next_permutation(p.begin(),p.end()))break;
	}
	cout<<ans<<endl;
	return 0;
}