#include <bits/stdc++.h>
#include "sequence.h"
using namespace std;
struct Segtree
{
struct Node
{
int64_t max_prefix_sum, max_suffix_sum, range_sum;
Node() { memset(this, 0, sizeof *this); }
};
vector<Node> t;
size_t l;
Segtree(size_t n)
{
l = 1 << (32 - __builtin_clz(n));
t.resize(2 * l);
}
Node combine(Node const &x, Node const &y)
{
Node z;
z.max_prefix_sum = max(x.max_prefix_sum, x.range_sum + y.max_prefix_sum);
z.max_suffix_sum = max(y.max_suffix_sum, y.range_sum + x.max_suffix_sum);
z.range_sum = x.range_sum + y.range_sum;
return z;
}
void update(int i, int x)
{
i += l;
t[i].max_prefix_sum = max(0, x);
t[i].max_suffix_sum = max(0, x);
t[i].range_sum = x;
while (i >>= 1)
t[i] = combine(t[i << 1], t[i << 1 | 1]);
}
Node query(int i, int j)
{
i += l, j += l;
Node x = Node(), y = Node();
while (i <= j)
{
if (i & 1)
x = combine(x, t[i++]);
if (!(j & 1))
y = combine(t[j--], y);
i >>= 1;
j >>= 1;
}
return combine(x, y);
}
};
int sequence(int N, vector<int> A)
{
for (int &x : A)
--x;
vector<vector<int>> occ(N);
for (int i = 0; i < N; ++i)
occ[A[i]].push_back(i);
Segtree tree_ge(N), tree_le(N);
for (int i = 0; i < N; ++i)
tree_ge.update(i, 1), tree_le.update(i, -1);
int ans = 0;
for (int i = 0; i < N; ++i)
{
for (int &j : occ[i])
tree_le.update(j, 1);
auto jt = occ[i].begin();
for (auto it = occ[i].begin(); it != occ[i].end(); ++it)
{
if (jt < it)
jt = it;
while (jt + 1 != occ[i].end())
{
if ((tree_ge.query(*it, *(jt + 1)).range_sum + tree_ge.query(0, *it - 1).max_suffix_sum +
tree_ge.query(*(jt + 1) + 1, N - 1).max_prefix_sum) *
(tree_le.query(*it, *(jt + 1)).range_sum + tree_le.query(0, *it - 1).max_suffix_sum +
tree_le.query(*(jt + 1) + 1, N - 1).max_prefix_sum) >=
0)
++jt;
else
break;
}
ans = max(ans, (int)(jt - it + 1));
}
for (int &j : occ[i])
tree_ge.update(j, -1);
}
return ans;
}
