#include "sequence.h"
#include "bits/stdc++.h"
#define ff first
#define ss second
#define pp pop_back
#define ll long long
#define pb push_back
#define ls(v) (int)v.size()
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define wr cout << "------------------------" << endl
using namespace std;
const int INF = 1e9 + 7;
const int N = 5e5 + 5;
int sgmax[N << 2];
int sgmin[N << 2];
int lz[N << 2];
int a[N];
vector<int> pos[N];
void push (int nd, int s, int e) {
if (lz[nd]) {
sgmin[nd] += lz[nd];
sgmax[nd] += lz[nd];
if (s != e) {
lz[nd << 1] += lz[nd];
lz[nd << 1 | 1] += lz[nd];
}
lz[nd] = 0;
}
}
void build (int nd, int s, int e) {
if (s == e) {
sgmax[nd] = sgmin[nd] = s;
return;
}
int mid = s + e >> 1;
build (nd << 1, s, mid);
build (nd << 1 | 1, mid + 1, e);
sgmax[nd] = max(sgmax[nd << 1], sgmax[nd << 1 | 1]);
sgmin[nd] = min(sgmin[nd << 1], sgmin[nd << 1 | 1]);
}
void upd (int nd, int s, int e, int l, int r, int val) {
push (nd, s, e);
if (s > r or l > e) return;
if (l <= s and e <= r) {
lz[nd] += val;
push (nd, s, e);
return;
}
int mid = s + e >> 1;
upd (nd << 1, s, mid, l, r, val);
upd (nd << 1 | 1, mid + 1, e, l, r, val);
sgmax[nd] = max(sgmax[nd << 1], sgmax[nd << 1 | 1]);
sgmin[nd] = min(sgmin[nd << 1], sgmin[nd << 1 | 1]);
}
int qrymin (int nd, int s, int e, int l, int r) {
push (nd, s, e);
if (s > r or l > e) return INF;
if (l <= s and e <= r) {
return sgmin[nd];
}
int mid = s + e >> 1;
int L = qrymin (nd << 1, s, mid, l, r);
int R = qrymin (nd << 1 | 1, mid + 1, e, l, r);
return min(L, R);
}
int qrymax (int nd, int s, int e, int l, int r) {
push (nd, s, e);
if (s > r or l > e) return -INF;
if (l <= s and e <= r) {
return sgmax[nd];
}
int mid = s + e >> 1;
int L = qrymax (nd << 1, s, mid, l, r);
int R = qrymax (nd << 1 | 1, mid + 1, e, l, r);
return max(L, R);
}
int sequence (int n, vector<int> A) {
for (int i = 1;i<=n;++i) pos[i].clear();
build (1, 0, n);
for (int i = 1;i<=n;++i) pos[A[i - 1]].pb(i);
int ans = 0;
for (int x = 1;x<=n;++x) {
if (pos[x].empty()) continue;
for (auto p : pos[x]) upd (1, 0, n, p, n, -1);
if (ls(pos[x]) == 2) {
int x1 = pos[x][0], x2 = pos[x][1];
int v2 = qrymax (1, 0, n, x2, n) - qrymin (1, 0, n, 0, x1 - 1);
int v1 = qrymin (1, 0, n, x2, n) - qrymax (1, 0, n, 0, x1 - 1);
if (v1 <= 2 and -2 <= v2) return 2;
}
for (auto p : pos[x]) upd (1, 0, n, p, n, -1);
}
return 1;
}
/*
7
1 2 3 1 2 3
9
1 1 2 3 4 3 2 1 1
14
2 6 2 5 3 4 2 1 4 3 5 6 3 2
*/
