#include <bits/stdc++.h>
using namespace std;
 
// O(N^3) naive
int solveNaive(vector<int> v) {
	const int n = v.size();
	int ans = 0;
	for (int i = 0; i < n; i++) {
		for (int j = i; j < n; j++) {
			unordered_map<int, int> cnt;
			int max_cnt = 0;
			for (int k = i; k <= j; k++) {
				cnt[v[k]]++;
				max_cnt = max(max_cnt, cnt[v[k]]);
			}
			if (max_cnt >= j-i-2) {
				ans = max(ans, j-i+1);
			}
		}
	}
	return ans;
}
 
// O(N^2) naive
int solveNaiveLittleOpt(vector<int> v) {
	const int n = v.size();
	int ans = 0;
	for (int i = 0; i < n; i++) {
		unordered_map<int, int> cnt;
		int max_cnt = 0;
		for (int j = i; j < n; j++) {
			cnt[v[j]]++;
			max_cnt = max(max_cnt, cnt[v[j]]);
			if (max_cnt >= j-i-2) {
				ans = max(ans, j-i+1);
			}
		}
	}
	return ans;
}
 
// O(NlgN)
int solve(vector<int> v) {
	unordered_map<int, int> cnt;
	multiset<int> pq;
	const int n = v.size();
	int l = 0, r = 0;
	int ans = 0;
	while (r < n) {
		cnt[v[r]]++;
		pq.insert(cnt[v[r]]);
		while(*pq.rbegin() < r-l-2) {
			auto iter = pq.find(cnt[v[l]]);
			pq.erase(iter);
			cnt[v[l]]--;
			pq.insert(cnt[v[l]]);
			l++;
		}
		ans = max(ans, r-l+1);
		r++;
	}
	return ans;
}
 
// O(N) given element of v is in [-10, 10]
int solveOpt(vector<int> v) {
	vector<int> cnt(21, 0);
	multiset<int> pq;
	const int n = v.size();
	int l = 0, r = 0;
	int ans = 0;
	while (r < n) {
		cnt[v[r]+10]++;
		while(*max_element(cnt.begin(), cnt.end()) < r-l-2) {
			cnt[v[l]+10]--;
			l++;
		}
		ans = max(ans, r-l+1);
		r++;
	}
	return ans;
}
 
int main() {
	cout<<solveOpt({-9, 8})<<endl;
	cout<<solveOpt({1, 1, -10, 3, -10, 3, -10})<<endl;
	cout<<solveOpt({2, 3, 3, 3, 3, 1})<<endl;
	cout<<solveOpt({3, 3, 2, 1, 2, 2, 9, 3, 3})<<endl;
	return 0;
}