#ifndef LOCAL
#pragma GCC optimize("O2")
#pragma GCC target("avx2")
#include "sequence.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define dbg(...)
#define STRUCT_DBG(...)
#else
#include "lib/debug.h"
#endif
using namespace std;
using namespace __gnu_pbds;
using ll = int;
using ld = long double;
using pll = pair<ll, ll>;
template <class T>
using vec = vector<T>;
using vll = vector<ll>;
using vpll = vector<pair<ll, ll>>;
using vvll = vector<vector<ll>>;
using vvpll = vector<vector<pair<ll, ll>>>;
template <class T>
using indexed_set =
tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define FOR(i, s, e) for (ll i = (ll)s; i < (ll)e; i++)
#define CFOR(i, s, e) for (ll i = (ll)s; i <= (ll)e; i++)
#define RFOR(i, e, s) for (ll i = (ll)e - 1; i >= (ll)s; i--)
#define TRAV(a, c) for (const auto &a : c)
#define all(x) x.begin(), x.end()
const ll MXN = 5e5 + 5;
ll n, suffmx[2 * MXN], suffmn[2 * MXN], prefmx[2 * MXN], prefmn[2 * MXN],
lsuff[2 * MXN], lprefmx[2 * MXN], lprefmn[2 * MXN];
vec<ll> inds[MXN];
#define lc(x) x + 1
#define rc(x) x + ((tm - tl + 1) << 1ll)
inline void pullsuff(ll v, ll tl, ll tr) {
if (tl == tr) return;
ll tm = (tl + tr) >> 1ll;
suffmx[v] = max(suffmx[lc(v)], suffmx[rc(v)]);
suffmn[v] = min(suffmn[lc(v)], suffmn[rc(v)]);
}
inline void pullpref(ll v, ll tl, ll tr) {
if (tl == tr) return;
ll tm = (tl + tr) >> 1ll;
prefmx[v] = max(prefmx[lc(v)], prefmx[rc(v)]);
prefmn[v] = min(prefmn[lc(v)], prefmn[rc(v)]);
}
inline void pushsuff(ll v, ll tl, ll tr) {
if (!lsuff[v]) return;
ll tm = (tl + tr) >> 1ll;
suffmx[v] += lsuff[v];
suffmn[v] += lsuff[v];
if (tl != tr) {
lsuff[lc(v)] += lsuff[v];
lsuff[rc(v)] += lsuff[v];
}
lsuff[v] = 0;
}
inline void pushpref(ll v, ll tl, ll tr) {
if (!lprefmx[v] && !lprefmn[v]) return;
ll tm = (tl + tr) >> 1ll;
prefmx[v] += lprefmx[v];
prefmn[v] += lprefmn[v];
if (tl != tr) {
lprefmx[lc(v)] += lprefmx[v];
lprefmx[rc(v)] += lprefmx[v];
lprefmn[lc(v)] += lprefmn[v];
lprefmn[rc(v)] += lprefmn[v];
}
lprefmx[v] = lprefmn[v] = 0;
}
void build(ll v, ll tl, ll tr) {
if (tl == tr) {
suffmx[v] = suffmn[v] = n - tl;
prefmx[v] = prefmn[v] = tl + 1;
} else {
ll tm = (tl + tr) >> 1ll;
build(lc(v), tl, tm);
build(rc(v), tm + 1, tr);
pullsuff(v, tl, tr);
pullpref(v, tl, tr);
}
}
void update_suff(ll v, ll tl, ll tr, ll r, ll x) {
ll tm = (tl + tr) >> 1ll;
pushsuff(v, tl, tr);
if (r < tl) return;
if (tr <= r) {
lsuff[v] += x;
pushsuff(v, tl, tr);
} else {
update_suff(lc(v), tl, tm, r, x);
if (tm + 1 <= r) {
update_suff(rc(v), tm + 1, tr, r, x);
} else {
pushsuff(rc(v), tm + 1, tr);
}
pullsuff(v, tl, tr);
}
}
void update_prefmx(ll v, ll tl, ll tr, ll l, ll x) {
ll tm = (tl + tr) >> 1ll;
pushpref(v, tl, tr);
if (tr < l) return;
if (l <= tl) {
lprefmx[v] += x;
pushpref(v, tl, tr);
} else {
if (tm >= l) {
update_prefmx(lc(v), tl, tm, l, x);
} else {
pushpref(lc(v), tl, tm);
}
update_prefmx(rc(v), tm + 1, tr, l, x);
pullpref(v, tl, tr);
}
}
void update_prefmn(ll v, ll tl, ll tr, ll l, ll x) {
ll tm = (tl + tr) >> 1ll;
pushpref(v, tl, tr);
if (tr < l) return;
if (l <= tl) {
lprefmn[v] += x;
pushpref(v, tl, tr);
} else {
if (tm >= l) {
update_prefmn(lc(v), tl, tm, l, x);
} else {
pushpref(lc(v), tl, tm);
}
update_prefmn(rc(v), tm + 1, tr, l, x);
pullpref(v, tl, tr);
}
}
inline void one_to_zero(ll ind) {
update_suff(0, 0, n - 1, ind, -1);
update_prefmn(0, 0, n - 1, ind, -2);
}
inline void zero_to_negone(ll ind) {
update_suff(0, 0, n - 1, ind, -1);
update_prefmx(0, 0, n - 1, ind, -2);
}
const pll query_suff(ll v, ll tl, ll tr, ll r) {
ll tm = (tl + tr) >> 1ll;
pushsuff(v, tl, tr);
if (r < tl) return {INT_MAX, INT_MIN};
if (tr <= r) {
return {suffmn[v], suffmx[v]};
} else {
pll o1 = query_suff(lc(v), tl, tm, r);
pll o2 = (tm + 1 <= r) ? query_suff(rc(v), tm + 1, tr, r)
: pll{INT_MAX, INT_MIN};
return {min(o1.first, o2.first), {max(o1.second, o2.second)}};
}
}
const vll query_point(ll v, ll tl, ll tr, ll ind) {
ll tm = (tl + tr) >> 1ll;
pushpref(v, tl, tr);
pushsuff(v, tl, tr);
if (tl == tr && tl == ind) {
return {prefmn[v], prefmx[v], suffmn[v], suffmx[v]};
} else {
if (ind <= tm) {
return query_point(lc(v), tl, tm, ind);
} else {
return query_point(rc(v), tm + 1, tr, ind);
}
}
};
ll walk_pref(ll v, ll tl, ll tr, ll l, ll r, ll la, ll ra) {
ll tm = (tl + tr) >> 1ll;
pushpref(v, tl, tr);
if (r < tl || tr < l || !(la <= prefmx[v] && prefmn[v] <= ra)) return l;
if (tl == tr) return tl;
ll o = walk_pref(rc(v), tm + 1, tr, l, r, la, ra);
if (o != l) return o;
return walk_pref(lc(v), tl, tm, l, r, la, ra);
};
int sequence(int _n, vector<int> a) {
n = _n;
FOR(i, 0, n) inds[a[i]].push_back(i);
build(0, 0, n - 1);
ll ans = 0;
CFOR(i, 1, n) {
if (inds[i].empty()) continue;
TRAV(e, inds[i]) one_to_zero(e);
TRAV(e, inds[i]) {
auto o1 = query_suff(0, 0, n - 1, e);
auto o2 = query_point(0, 0, n - 1, e);
ll la = -(o1.first - o2[2] - o2[0]) + 1;
ll ra = -(o1.second - o2[3] - o2[1]) - 1;
swap(la, ra);
ll best = walk_pref(0, 0, n - 1, e, n - 1, la, ra);
auto it1 = upper_bound(all(inds[i]), best);
auto it2 = lower_bound(all(inds[i]), e);
ans = max(ans, (ll)(it1 - it2));
}
TRAV(e, inds[i]) zero_to_negone(e);
}
return ans;
}
int main() {
int N;
assert(1 == scanf("%d", &N));
std::vector<int> A(N);
for (int i = 0; i < N; ++i) {
assert(1 == scanf("%d", &A[i]));
}
int result = sequence(N, A);
printf("%d\n", result);
return 0;
}
Compilation message
/usr/bin/ld: /tmp/cc25cjpA.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccPFdYxw.o:sequence.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
