#include "sequence.h"
#include <bits/extc++.h>
#define int long long
#define emb emplace_back
#define pii pair <int32_t, int32_t>
#define tiii tuple <int32_t, int32_t, int32_t>
#define all(a) a.begin(), a.end()
using namespace std;
using namespace __gnu_pbds;
#define ordered_multiset tree <int, null_type, less_equal <int>, rb_tree_tag, tree_order_statistics_node_update>
const int N = 5e5 + 5;
const int inf = 1e18;
int n, a[N], b[N];
struct lazyseg {
int lazy[4 * N], mnseg[4 * N], mxseg[4 * N];
void push(int l, int r, int i){
mnseg[i] += lazy[i];
mxseg[i] += lazy[i];
if (l != r) lazy[2 * i] += lazy[i], lazy[2 * i + 1] += lazy[i];
lazy[i] = 0;
}
void build(int l, int r, int i){
if (l == r) return mnseg[i] = mxseg[i] = b[l], void();
int mid = (l + r) / 2;
build(l, mid, 2 * i), build(mid + 1, r, 2 * i + 1);
mnseg[i] = min(mnseg[2 * i], mnseg[2 * i + 1]);
mxseg[i] = max(mxseg[2 * i], mxseg[2 * i + 1]);
}
void update(int l, int r, int i, int ll, int rr, int val){
push(l, r, i);
if (l >= ll && r <= rr) return lazy[i] += val, push(l, r, i), void();
if (r < ll || l > rr) return;
int mid = (l + r) / 2;
update(l, mid, 2 * i, ll, rr, val);
update(mid + 1, r, 2 * i + 1, ll, rr, val);
mxseg[i] = max(mxseg[2 * i], mxseg[2 * i + 1]);
mnseg[i] = max(mnseg[2 * i], mnseg[2 * i + 1]);
}
int mnquery(int l, int r, int i, int ll, int rr){
push(l, r, i);
if (l >= ll && r <= rr) return mnseg[i];
if (r < ll || l > rr) return inf;
int mid = (l + r) / 2;
return min(mnquery(l, mid, 2 * i, ll, rr), mnquery(mid + 1, r, 2 * i + 1, ll, rr));
}
int mxquery(int l, int r, int i, int ll, int rr){
push(l, r, i);
if (l >= ll && r <= rr) return mxseg[i];
if (r < ll || l > rr) return 0;
int mid = (l + r) / 2;
return max(mxquery(l, mid, 2 * i, ll, rr), mxquery(mid + 1, r, 2 * i + 1, ll, rr));
}
} seg;
int32_t sequence(int32_t Nn, vector<int32_t> A) {
n = Nn;
map <int, vector <int>> mp;
for (int i = 0; i < n; i++) {
a[i + 1] = A[i];
b[i + 1] = 1 + b[i];
mp[a[i + 1]].emb(i + 1);
}
for (auto [val, vec] : mp) {
if (vec.size() >= 2) {
int sz = vec.size();
seg.update(1, n, 1, vec[0], n, -1);
seg.update(1, n, 1, vec[1], n, -1);
int lmn = seg.mnquery(1, n, 1, 1, vec[0]);
int lmx = seg.mxquery(1, n, 1, 1, vec[0]);
int rmn = seg.mnquery(1, n, 1, vec[1], n);
int rmx = seg.mxquery(1, n, 1, vec[1], n);
if (rmn <= lmx && lmx <= rmx) return 2;
seg.update(1, n, 1, vec[0], n, -1);
seg.update(1, n, 1, vec[1], n, -1);
}
else seg.update(1, n, 1, vec[0], n, -1), seg.update(1, n, 1, vec[0], n, -1);
}
return 1;
}
