#include "sequence.h"
#include<bits/stdc++.h>
using namespace std;
#define in pair<int, int>
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define INF (int)1e6
#define MX (int)3e5+5
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)
in extremise(const in &a, const in&b)
{
return {min(a.f, b.f), max(a.s, b.s)};
}
void increment(int delta, in &a)
{
if(a.f == INF)
return;
a.f+=delta;
a.s+=delta;
return;
}
struct extremal_tree
{
vector<in> tree;
void init(int n)
{
tree.assign(4*n+8, {INF, -INF});
return;
}
void upd(int v, int pos, int id, int l, int r)
{
if(l == r)
{
tree[id] = extremise(tree[id], {v, v});
return;
}
int m = (l+r)/2;
if(pos <= m)
upd(v, pos, 2*id, l, m);
else
upd(v, pos, 2*id+1, m+1, r);
tree[id] = extremise(tree[2*id], tree[2*id+1]);
return;
}
in val(int ql, int qr, int id, int l, int r)
{
if(r < ql || qr < l)
return {INF, -INF};
if(ql <= l && r <= qr)
return tree[id];
int m = (l+r)/2;
in a = val(ql, qr, 2*id, l, m);
in b = val(ql, qr, 2*id+1, m+1, r);
return extremise(a, b);
}
};
struct lazy_extremal_tree
{
vector<in> tree;
vector<int> lazy;
void init(int n)
{
tree.assign(4*n+8, {INF, -INF});
lazy.assign(4*n+8, 0);
return;
}
void push(int id)
{
increment(lazy[id], tree[2*id]);
increment(lazy[id], tree[2*id+1]);
lazy[2*id]+=lazy[id];
lazy[2*id+1]+=lazy[id];
lazy[id] = 0;
return;
}
void upd(int v, int pos, int id, int l, int r)
{
if(l == r)
{
tree[id] = extremise(tree[id], {v, v});
return;
}
int m = (l+r)/2;
if(pos <= m)
upd(v, pos, 2*id, l, m);
else
upd(v, pos, 2*id+1, m+1, r);
tree[id] = extremise(tree[2*id], tree[2*id+1]);
return;
}
void upd2(int delta, int ql, int qr, int id, int l, int r)
{
if(qr < l || r < ql)
return;
if(ql <= l && r <= qr)
{
lazy[id]+=delta;
increment(delta, tree[id]);
return;
}
push(id);
int m = (l+r)/2;
upd2(delta, ql, qr, 2*id, l, m);
upd2(delta, ql, qr, 2*id+1, m+1, r);
tree[id] = extremise(tree[2*id], tree[2*id+1]);
return;
}
in val(int ql, int qr, int id, int l, int r)
{
if(r < ql || qr < l)
return {INF, -INF};
if(ql <= l && r <= qr)
return tree[id];
push(id);
int m = (l+r)/2;
in a = val(ql, qr, 2*id, l, m);
in b = val(ql, qr, 2*id+1, m+1, r);
return extremise(a, b);
}
};
vector<int> compressor;
int compress(int n)
{
return lower_bound(compressor.begin(), compressor.end(), n)-compressor.begin();
}
int solve(int n, vector<in> &ac, vector<in> &bd)//no assuming compression!
{
extremal_tree work;
compressor.clear();
work.init(2*n);
vector<int> v;
//compress begin
for(auto [a, c]: ac)
v.pb(c);
for(auto [b, d]: bd)
v.pb(d);
sort(v.begin(), v.end());
compressor.pb(v[0]);
for(int k = 1; k < v.size(); k++)
{
if(v[k] != v[k-1])
compressor.pb(v[k]);
}
//compress over
vector<in> a;
vector<in> b;
for(int i = 0; i < n; i++)
a.pb({ac[i].f, i});
for(int i = 0; i < n; i++)
b.pb({bd[i].f, i});
sort(a.begin(), a.end());
sort(b.begin(), b.end());
int ans = -INF;
int l = 0;
for(int i = 0; i < n; i++)
{
while((l < n) && (a[l].f <= b[i].f))
{
work.upd(a[l].s, compress(ac[a[l].s].s), 1, 0, 2*n);
l++;
}
auto [m, M] = work.val(0, compress(bd[b[i].s].s), 1, 0, 2*n);
if(m != INF)
ans = max(abs(m-b[i].s), ans);
if(M != -INF)
ans = max(abs(M-b[i].s), ans);
}
return ans;
}
int sequence(int n, vector<int> a)
{
lazy_extremal_tree work;
work.init(n);
vector<int> adj[n+1];
for(int i = 1; i <= n; i++)
adj[a[i-1]].pb(i);
for(int i = 0; i <= n; i++)
work.upd(-i, i, 1, 0, n);
int ans = 0;
for(int i = 1; i <= n; i++)
{
int m = adj[i].size();
for(int k: adj[i-1])
work.upd2(+1, k, n, 1, 0, n);
for(int k: adj[i])
work.upd2(+1, k, n, 1, 0, n);
vector<int> bb(m+2);
bb[0] = 0;
bb[m+1] = n+1;
for(int j = 1; j <= m; j++)
bb[j] = adj[i][j-1];
vector<in> ac(m+1), bd(m+1);
for(int j = 0; j <= m; j++)
{
auto [a, b] = work.val(bb[j], bb[j+1]-1, 1, 0, n);
ac[j] = {a+j, j-b};
bd[j] = {b+j, j-a};
}
int ok = solve(m+1, ac, bd);
ans = max(ans, ok);
}
return ans;
}
/*vector<int> c;
int W(int l, int r, int x)
{
int cnt = 0;
for(int i = l; i <= r; i++)
cnt+=(c[i] == x);
return cnt;
}
int median_freq(int l, int r)
{
vector<int> v;
int k = r-l;
for(int i = l; i <= r; i++)
v.pb(c[i]);
sort(v.begin(), v.end());
int t = k/2;
int tp = t+k%2;
return max(W(l, r, v[t]), W(l, r, v[tp]));
}
signed main()
{
fast();
int t;
cin >> t;
while(t--)
{
c.clear();
int n;
cin >> n;
vector<int> a(n);
for(int &k: a)
{
cin >> k;
c.pb(k);
}
int ans = sequence(n, a);
int tit = 0;
for(int l = 0; l < n; l++)
{
for(int r = l; r < n; r++)
tit = max(tit, median_freq(l, r));
}
if(ans != tit)
{
cout << "WTF !!!" << endl;
printf("Fake = %d, real = %d", ans, tit);
}
assert(ans==tit);
cout << "All good!" << endl;
}
return 0;
}*/
