#ifndef Nhoksocqt1
#include "sequence.h"
#endif // Nhoksocqt1
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;
template<class X, class Y>
inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
return uniform_int_distribution<int>(l, r)(rng);
}
const int MAXN = 500005;
vector<int> B[MAXN];
int fen[2 * MAXN], fenp[2 * MAXN];
int val[MAXN], cnt[MAXN], nArr;
int sub2(void) {
int res(1);
for (int l = 1; l <= nArr; ++l) {
set<int> Set;
int pos(val[l]), cntPos(1);
Set.insert(pos);
++cnt[pos];
for (int r = l + 1; r <= nArr; ++r) {
cntPos += (val[r] <= pos);
if(++cnt[val[r]] == 1)
Set.insert(val[r]);
while(cntPos < (r - l + 1) / 2 + 1) {
auto it = Set.lower_bound(pos); ++it;
assert(it != Set.end());
pos = *it;
cntPos += cnt[pos];
}
while(cntPos - cnt[pos] >= (r - l + 1) / 2 + 1) {
cntPos -= cnt[pos];
auto it = Set.lower_bound(pos);
assert(it != Set.begin()); --it;
pos = *it;
}
//cout << l << ' ' << r << ' ' << pos << ' ' << cntPos << '\n';
res = max(res, cnt[pos]);
if((r - l + 1) % 2 == 0 && cntPos - cnt[pos] >= (r - l + 1) / 2) {
auto it = Set.lower_bound(pos);
assert(it != Set.begin()); --it;
res = max(res, cnt[*it]);
}
}
for (int r = l; r <= nArr; ++r)
--cnt[val[r]];
}
return res;
}
int sub3(void) {
int res(0);
for (int i = 1; i <= nArr; ) {
int j(i);
while(j <= nArr && val[j] == val[i])
++j;
res = max(res, j - i);
i = j;
}
for (int i = 1; i <= nArr; ++i)
++cnt[val[i]];
int j(nArr);
for (int i = 1; i <= j; ++i) {
if(i > 1 && val[i] == val[i - 1])
continue;
while(j > i && val[j] < val[i])
--cnt[val[j--]];
if(j > i && val[i] == val[j]) {
int cntPos = cnt[val[i]];
if(cnt[val[i]] + i - 1 + nArr - j >= (nArr + 1) / 2)
res = max(res, cnt[val[i]]);
}
}
return res;
}
void modify(int fen[], int i, int v) {
for (i += nArr + 1; i <= 2 * nArr + 1; i += i & -i)
fen[i] += v;
}
int get(int fen[], int i) {
int res(0);
for (i += nArr + 1; i > 0; i -= i & -i)
res += fen[i];
return res;
}
bool check4(int minCnt, int x) {
for (int i = 1; i <= 2 * nArr; ++i)
fen[i] = fenp[i] = 0;
ll res(0);
int j(1), cnt(0), sumx(0), sumpx(0), sumxj(0), sumpxj(0);
for (int i = 1; i <= nArr; ++i) {
cnt += (val[i] == x);
while(j <= i && cnt >= minCnt) {
cnt -= (val[j] == x);
modify(fen, sumxj, +1);
modify(fenp, sumpxj, +1);
sumxj += 2 * (val[j] <= x) - 1;
sumpxj += 2 * (val[j] < x) - 1;
++j;
}
sumx += 2 * (val[i] <= x) - 1;
sumpx += 2 * (val[i] < x) - 1;
res += get(fen, sumx) - get(fenp, sumpx);
}
return (res > 0);
}
int sub4(void) {
int res(1);
for (int i = 1; i <= 3; ++i) {
int l(2), r(nArr);
while(l <= r) {
int mid = (l + r) >> 1;
if(check4(mid, i)) {
res = max(res, mid);
l = mid + 1;
} else {
r = mid - 1;
}
}
}
return res;
}
struct SegNode {
int minv, maxv, lz;
} seg[4 * MAXN];
inline void pushDown(int id) {
int &lz(seg[id].lz);
id <<= 1;
seg[id] = {seg[id].minv + lz, seg[id].maxv + lz, seg[id].lz + lz};
seg[id | 1] = {seg[id | 1].minv + lz, seg[id | 1].maxv + lz, seg[id | 1].lz + lz};
lz = 0;
}
void update(int id, int l, int r, int u, int v, int k) {
if(u <= l && r <= v) {
seg[id] = {seg[id].minv + k, seg[id].maxv + k, seg[id].lz + k};
return;
}
if(seg[id].lz)
pushDown(id);
int mid = (l + r) >> 1;
if(mid >= u)
update(id << 1, l, mid, u, v, k);
if(mid + 1 <= v)
update(id << 1 | 1, mid + 1, r, u, v, k);
seg[id].minv = min(seg[id << 1].minv, seg[id << 1 | 1].minv);
seg[id].maxv = max(seg[id << 1].maxv, seg[id << 1 | 1].maxv);
}
ii query(int id, int l, int r, int u, int v) {
if(u <= l && r <= v)
return make_pair(seg[id].minv, seg[id].maxv);
if(seg[id].lz)
pushDown(id);
ii res = {1e9, -1e9};
int mid = (l + r) >> 1;
if(mid >= u)
res = query(id << 1, l, mid, u, v);
if(mid + 1 <= v) {
ii qr = query(id << 1 | 1, mid + 1, r, u, v);
res = {min(res.fi, qr.fi), max(res.se, qr.se)};
}
return res;
}
int sub5(void) {
for (int i = 1; i <= nArr; ++i) {
B[val[i]].push_back(i);
update(1, 1, nArr, i, i, -i);
}
int res(1);
for (int i = 1; i <= nArr; ++i) {
if(!sz(B[i]))
continue;
for (int it = 0; it < sz(B[i]); ++it) {
int j(B[i][it]);
update(1, 1, nArr, j, nArr, +2);
}
if(sz(B[i]) != 2)
continue;
int l = B[i][0], r = B[i][1];
ii qrL = (l > 1) ? query(1, 1, nArr, 1, l - 1) : ii(1e9, -1e9), qrR = query(1, 1, nArr, r, nArr);
qrL.fi = min(qrL.fi, 0), qrL.se = max(qrL.se, 0);
//cout << i << ' ' << l << ' ' << r << ' ' << qrL.fi << ' ' << qrL.se << ' ' << qrR.fi << ' ' << qrR.se << '\n';
if(qrR.se - qrL.fi >= 0 && qrR.fi - qrL.se <= 1) {
res = 2;
break;
}
}
return res;
}
int sequence(int _N, vector<int> _A) {
nArr = _N;
bool check5(1);
for (int i = 1; i <= nArr; ++i) {
val[i] = _A[i - 1];
check5 &= (++cnt[val[i]] <= 2);
}
bool check3(1);
for (int i = 1; i <= nArr; ++i) {
check3 &= (i <= 2 || val[i - 2] <= val[i - 1] || val[i - 2] >= val[i - 1] && val[i - 1] >= val[i]);
cnt[i] = 0;
}
//cout << sub5() << '\n';
if(nArr <= 2000) {
return sub2();
} else
if(check3) {
return sub3();
} else
if(*max_element(val + 1, val + nArr + 1) <= 3) {
return sub4();
} else
if(check5) {
return sub5();
}
}
#ifdef Nhoksocqt1
int main(void) {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define TASK "sequence"
if(fopen(TASK".inp", "r")) {
freopen(TASK".inp", "r", stdin);
freopen(TASK".out", "w", stdout);
}
vector<int> _A;
int _N;
cin >> _N;
_A.resize(_N);
//vector<int> _B; for (int i = 0; sz(_B) < _N; ++i) {int x = Random(1, 2); _B.push_back(i + 1); if(sz(_B) < _N && x > 1) _B.push_back(i + 1); } shuffle(_B.begin(), _B.end(), rng);
for (int i = 0; i < _N; ++i) {
cin >> _A[i];
//_A[i] = _B[i]; cout << _A[i] << " \n"[i + 1 == _N];
}
int ans = sequence(_N, _A);
cout << "ANSWER: " << ans << '\n';
return 0;
}
#endif // Nhoksocqt1
