The number of occurrences of each integers is invariant under the operation, so the final weakly-monotonically-state is uniquely determined as the sorted \(A\). Let this be \(B=(B_1,B_2,\ldots,B_N)\).
Additionally, let \(C_{i,j}\) \((1\leq i,j\leq 4)\) be the number of integers \(1\leq k\leq N\) such that \(A_k=i\) and \(B_k=j\).
Here, for a permutation \(p=(p_1,p_2,p_3,p_4)\) of \((1,2,3,4)\), consider the quantity

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

Now, we will show that an operation decreases \(f(p)\) at most by one. Suppose that a pair \((i, j)\) such that \(A_i=p_w\), \(B_i=p_x\), \(A_j=p_y\), \(B_j=p_z\) was used for an operation. Then, \(C_{p_w,p_x}\) and \(C_{p_y,p_z}\) decreases by one, while \(C_{p_y,p_x}\) and \(C_{p_w,p_z}\) increases by one. Thus, \(f(p)\) decreases at most by two; in order for \(C_{p_w,p_x}\) and \(C_{p_y,p_z}\) to be both decreased, \(w<x\) and \(y<z\) are necessary. However, if \(w\leq y\), then \(w<z\); if \(w>y\), then \(y<x\); in any case, it decreases only by one overall. Therefore, at least

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

operations are required, where the argument \(p\) of \(\max\) spans over all permutations of \((1,2,3,4)\).

Next, we show that the performing the operation this number of times always makes it weakly monotonically increasing. First, for each \(i\neq j\), we repeatedly choose \(k\) and \(k'\) such that \(A_k=i\) and \(B_k=j\), and \(A_{k'}=j\) and \(B_{k'}=i\) and perform the operation, as long us such a pair exists. This operation decreases \(C_{k,k'}\) and \(C_{k',k}\) by one, while increases \(C_{k,k}\) and \(C_{k',k'}\), so the value \(f(p)\) mentioned above is decreased exactly by one (independent of \(p\)).

Once the repetition is over, for each \(i\neq j\), at least one of \(C_{i,j}\) and \(C_{j,i}\) is \(0\). Now, let us consider a four-vertex graph \(G\) such that, at this point, there is a directed edge from vertex \(i\) to vertex \(j\) with weight \(C_{i,j}\) if and only if \(C_{i,j}>0\), for each \(i\neq j\).
First, we consider the case where \(G\) has six edges (there is no \(i\neq j\) such that \(C_{i,j}=C_{j,i}=0\)). Then, ignoring the weights, the graph is uniquely determined up to isomorphism; i.e. swapping the vertex labels, we can always obtain the same graph. We first prove this claim. \(G\) satisfies:

• For all pairs of different vertices, there is an edge in only one direction.
• The indegree and outdegree of each vertex is \(1\) or \(2\).

The latter follows because the occurrences of each number in \(A\) and \(B\) are equal, and \(\displaystyle\sum_{j=1}^4C_{i,j}=\displaystyle\sum_{j=1}^4C_{j,i}\) for each \(1\leq i\leq 4\), thus for all vertices, (sum of weights of edges towards the vertex)\(=\)(sum of weights of edges from the vertex) should hold \(\cdots(I)\).

Here, there are exactly two vertices of outdegree two; denote them by vertices \(p_1\) and \(p_2\). Assign vertex labels to them so that the edge goes from \(p_1\) to \(p_2\). Also assign vertex labels to vertices \(p_3\) and \(p_4\), whose indegree should be \(2\), so that the directed edge between them goes from \(p_3\) to \(p_4\). Then, by the conditions above, the edges turn out to be going:

• edge \(1\): vertex \(p_1\) \(\to \) vertex \(p_3\)
• edge \(2\): vertex \(p_2\) \(\to \) vertex \(p_3\)
• edge \(3\): vertex \(p_2\) \(\to \) vertex \(p_4\)
• edge \(4\): vertex \(p_1\) \(\to \) vertex \(p_2\)
• edge \(5\): vertex \(p_3\) \(\to \) vertex \(p_4\)
• edge \(6\): vertex \(p_4\) \(\to \) vertex \(p_1\).

Moreover, if we let \(W_1\), \(W_2\), and \(W_3\) be the weights of edges \(1\), \(2\), and \(3\), respectively, then by \((I)\), the weights of edges \(4\), \(5\), and \(6\) are, respectively, \(W_2+W_3\), \(W_1+W_2\), and \(W_1+W_2+W_3\). Then, the following operations are possible:

• Choose \((k_1,k_2,k_3)\) such that \(A_{k_1}=p_1\) and \(B_{k_1}=p_3\), \(A_{k_2}=p_3\) and \(B_{k_2}=p_4\), and \(A_{k_3}=p_4\) and \(B_{k_3}=p_1\), and perform operations with \((i,j)=(k_1,k_2), (k_2,k_3)\). Repeat this \(W_1\) times.

• Choose \((k_1,k_2,k_3,k_4)\) such that \(A_{k_1}=p_2\) and \(B_{k_1}=p_3\), \(A_{k_2}=p_3\) and \(B_{k_2}=p_4\), \(A_{k_3}=p_4\) and \(B_{k_3}=p_1\), and \(A_{k_4}=p_1\) and \(B_{k_4}=p_2\), and perform operations with \((i,j)=(k_1,k_2), (k_2,k_3), (k_3,k_4)\). Repeat this \(W_2\) times.

• Choose \((k_1,k_2,k_3)\) such that \(A_{k_1}=p_2\) and \(B_{k_1}=p_4\), \(A_{k_2}=p_4\) and \(B_{k_2}=p_1\), and \(A_{k_3}=p_1\) and \(B_{k_3}=p_2\), and perform operations with \((i,j)=(k_1,k_2), (k_2,k_3)\). Repeat this \(W_3\) times.

For all of these operations, we never choose the same index as \(k_\alpha\) \((\alpha=1,2,3,4)\) more than once. These operations are possible by definition of \(G\), and they make \(A\) weakly monotonically increasing in the end. Here, \(\displaystyle\sum_{i=1}^4\displaystyle\sum_{j=i+1}^{4} C_{p_i,p_j} \) decreases by one for each operation, so the total number of operations is \(\displaystyle\sum_{i=1}^4\displaystyle\sum_{j=i+1}^{4} C_{p_i,p_j} \); thus, the minimum number of operations required is at most

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

On the other hand, if \(G\) has less than six edges, there are two graphs with five edges and one graph for three or four edges, up to isomorphism, but all of these graphs can be obtained by removing appropriate edges from the six-edge graph considered above; by adding an edge with weight \(0\) in a proper direction between (different) vertices between which there is no edge, it boils down to the case where one or more of \(W_1\), \(W_2\), and \(W_3\) is zero. Therefore, the number of operations required here is still at most \( \displaystyle\max_p \left(\sum_{i=1}^4\sum_{j=i+1}^{4} C_{p_i,p_j} \right) \) . Since this coincides with the lower bound that we found before, the answer turns out to be

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

Finding \(B\) requires \(O(N)\) time (or \(O(N \log N)\) time if you use the ordinary sorting algorithm); finding \(C\) requires \(O(N)\) time, and the iteration over permutations and summation are \(O(1)\) time (independent of \(N\), it is about \(4!\times \frac{4\cdot 5}{2}=240\)); hence, the total complexity is \(O(N)\), which is fast enough to solve this problem.

Sample code in 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;
}