#include "sequence.h"
#include <algorithm>
#include <vector>
using namespace std;
struct Node
{
int sum, neg, pos;
};
Node nodes[2000005];
struct Sus
{
int mn;
bool r;
};
Sus sussy[13000005];
void wind() { sussy[1].r = true; }
void clean(int i)
{
auto &node = sussy[i];
if (node.r)
{
node.mn = 1e9;
sussy[2 * i].r = true;
sussy[2 * i + 1].r = true;
node.r = false;
}
}
void simple_upd(int i, int l, int r, int p, int x)
{
clean(i);
auto &node = sussy[i];
if (p < l or p > r)
return;
if (l == r)
{
node.mn = min(node.mn, x);
return;
}
int m = l + (r - l) / 2;
simple_upd(2 * i, l, m, p, x);
simple_upd(2 * i + 1, m + 1, r, p, x);
node.mn = min(sussy[2 * i].mn, sussy[2 * i + 1].mn);
}
int simple_query(int i, int l, int r, int ql, int qr)
{
clean(i);
if (qr < l or ql > r)
return 1e9;
if (ql <= l and qr >= r)
return sussy[i].mn;
// int m = (l + r) / 2;
int m = l + (r - l) / 2;
return min(simple_query(2 * i, l, m, ql, qr),
simple_query(2 * i + 1, m + 1, r, ql, qr));
}
// struct Sus
// {
// int mn, lazy;
// bool r;
// };
//
// Sus sussy[8000005];
//
// void wind() {
// sussy[1].r = true;
// }
//
// void clean(int i) {
// auto &node = sussy[i];
// if (node.r)
// {
// node.mn = 1e9;
// node.lazy = 1e9;
// sussy[2 * i].r = true;
// sussy[2 * i + 1].r = true;
// node.r = false;
// }
// node.mn = min(node.mn, node.lazy);
// sussy[2 * i].lazy = min(sussy[2 * i].lazy, node.lazy);
// sussy[2 * i + 1].lazy = min(sussy[2 * i + 1].lazy, node.lazy);
// }
//
// int set_query(int i, int l, int r, int ql, int qr, int v) {
// clean(i);
// auto &node = sussy[i];
// if (qr < l or ql > r)
// return 1e9;
// if (ql <= l and qr >= r)
// {
// node.lazy = min(node.lazy, v);
// clean(i);
// return node.mn;
// }
// // int m = (l + r) / 2;
// int m = l + (r - l) / 2;
// auto a = set_query(2 * i, l, m, ql, qr, v);
// auto b = set_query(2 * i + 1, m + 1, r, ql, qr, v);
// node.mn = min(sussy[2 * i].mn, sussy[2 * i + 1].mn);
// return min(a, b);
// }
void reset()
{
for (auto &x : nodes)
x.sum = x.neg = x.pos = 0;
}
Node comb(const Node &a, const Node &b)
{
return {a.sum + b.sum, min(a.neg, a.sum + b.neg),
max(a.pos, a.sum + b.pos)};
}
void upd(int i, int l, int r, int p, int x)
{
if (p < l or p > r)
return;
auto &node = nodes[i];
if (l == r)
{
node.sum = x;
node.neg = min(x, 0);
node.pos = max(x, 0);
return;
}
int m = (l + r) / 2;
upd(2 * i, l, m, p, x);
upd(2 * i + 1, m + 1, r, p, x);
node = comb(nodes[2 * i], nodes[2 * i + 1]);
}
Node query(int i, int l, int r, int ql, int qr)
{
if (qr < l or ql > r)
return {0, 0, 0};
if (ql <= l and qr >= r)
return nodes[i];
int m = (l + r) / 2;
return comb(query(2 * i, l, m, ql, qr),
query(2 * i + 1, m + 1, r, ql, qr));
}
vector<int> possy[500005];
constexpr int L = -1e6 - 5;
constexpr int R = -L;
int sequence(int N, vector<int> A)
{
reset();
for (auto &a : possy)
a.clear();
for (int i = 0; i < N; i++)
{
possy[A[i]].push_back(i);
upd(1, 0, N - 1, i, 1);
}
int ans = 1;
// for (int i = L; i <= R; i++)
// simple_upd(1, L, R, i, 1e9, true);
for (int q = 1; q <= N; q++)
{
auto &b = possy[q];
if (b.empty())
continue;
b.push_back(N);
vector<pair<int, int>> segs;
int bg = 0;
int ptr = 0;
for (int p : b)
{
auto h = query(1, 0, N - 1, bg, p - 1);
segs.push_back({ptr + h.neg, ptr + h.pos});
ptr += h.sum;
bg = p + 1;
}
int m = (int)segs.size();
wind();
vector<tuple<int, int, int>> from, to;
for (int i = 0; i < m; i++)
{
auto [a, b] = segs[i];
from.push_back({a + i, b - i, i});
to.push_back({b + i, a - i, i});
}
sort(from.begin(), from.end());
sort(to.begin(), to.end());
ptr = 0;
for (auto [b, a, i] : to)
{
while (ptr < (int)from.size() and
get<0>(from[ptr]) <= b)
{
auto [p, q, j] = from[ptr];
simple_upd(1, L, R, q, j);
ptr++;
}
int g = simple_query(1, L, R, a, R);
ans = max(ans, i - g);
}
// for (auto [p, q, j] : from)
// {
// simple_upd(1, L, R, q, 1e9, true);
// }
// for (int i = 0; i < m; i++)
// {
// auto [a, b] = segs[i];
// int f = set_query(1, -1e6 - 5, 1e6 + 5, a - i, b + i,
// i); ans = max(ans, i - f);
// }
// for (int i = 0; i < m; i++)
// {
// for (int j = i + 1; j < m; j++)
// {
// int d = j - i;
// auto [a, b] = segs[i];
// auto [x, y] = segs[j];
// if (not (a > y + d or b < x - d))
// {
// ans = max(ans, d);
// }
// }
// }
for (int p : b)
upd(1, 0, N - 1, p, -1);
}
return ans;
}
