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

const int inf = 2e9;

namespace {
	vector<int> cnt(4, 0);
	vector<vector<int>> lst(4);
}

bool check(int x, int y, bool trace = false){
	// Find first x 1s and last x 3s
	// Find first y 3s and last y 1s
	
	if (x + y > cnt[1] || x + y > cnt[3]) return false;
	
	vector<int> L13, R13, L31, R31;
	
	for (int i = 0; i < x; i++) L13.push_back(lst[1][i]);
	for (int i = 0; i < x; i++) R13.push_back(lst[3].end()[-(i+1)]);

	for (int i = 0; i < y; i++) L31.push_back(lst[3][i]);
	for (int i = 0; i < y; i++) R31.push_back(lst[1].end()[-(i+1)]);

	reverse(R13.begin(), R13.end());
	reverse(R31.begin(), R31.end());

	// Check if valid
	for (int i = 0; i < x; i++){
		if (L13[i] > R13[i]) return false;
	}
	for (int i = 0; i < y; i++){
		if (L31[i] > R31[i]) return false;
	}

	int itl_13 = 0, itl_31 = 0;
	int itr_13 = 0, itr_31 = 0;

	for (auto pos: lst[2]){
		while (itr_13 < x && L13[itr_13] < pos){
			itr_13++;
		}
		while (itr_31 < y && L31[itr_31] < pos){
			itr_31++;
		}

		pair<int, int> choice = {inf, 0};
		if (itl_13 < itr_13){
			if (R13[itl_13] < pos) return false;
			choice = min(choice, pair{R13[itl_13], 1});
		}
		if (itl_31 < itr_31){
			if (R31[itl_31] < pos) return false;
			choice = min(choice, pair{R31[itl_31], 2});
		}

		if (choice.second == 1){
			if (trace){
				answer(L13[itl_13], pos, R13[itl_13]);
			}
			itl_13++;
		}
		else if (choice.second == 2){
			if (trace){
				answer(L31[itl_31], pos, R31[itl_31]);
			}
			itl_31++;
		}
	}

	return itl_13 == x && itl_31 == y;
}

void maximize(vector<int> A){
	int n = A.size();

	for (int i = 0; i < n; i++) cnt[A[i]]++;
	for (int i = 0; i < n; i++) lst[A[i]].push_back(i);

	int x = min(cnt[1], cnt[3]), y = 0;
	pair<int, int> opt = {0, 0};
	while (x >= 0){
		bool success = check(x, y);
		if (success){
			if (x + y > opt.first + opt.second) opt = {x, y};
			y++;
		}
		else{
			x--;
		}
	}

	// cout << "Answer: " << opt.first << " " << opt.second << endl;
	check(opt.first, opt.second, true);
}