一次又一次地找到 hack 数据,已力竭,跪求条/ll
#include <bits/stdc++.h>
#define int long long
#define ls k << 1
#define rs k << 1 | 1
const int N = 5e5 + 5, base = 23333, mod = 998244353;
int n, a[N], b[N];
struct node {
int l, r;
int h1, h2;
} c[N << 2];
int read() {
int res = 0, i = 1;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-') i = -i;
c = getchar();
}
while (c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = getchar();
}
return res * i;
}
void write(int x) {
if (x < 0) {
putchar('-');
x = -x;
}
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
}
void build(int k, int l, int r) {
c[k].l = l, c[k].r = r;
c[k].h1 = c[k].h2 = 0;
if (l == r) return;
int mid = l + r >> 1;
build(ls, l, mid);
build(rs, mid + 1, r);
}
void pushup(int k) {
c[k].h1 = c[ls].h1 * b[c[rs].r - c[rs].l + 1] % mod + c[rs].h1;
c[k].h2 = c[rs].h2 * b[c[ls].r - c[ls].l + 1] % mod + c[ls].h2;
}
void modify(int k, int pos) {
if (c[k].l == c[k].r) {
c[k].h1 = c[k].h2 = 1;
return;
}
int mid = c[k].l + c[k].r >> 1;
if (pos <= mid) modify(ls, pos);
else modify(rs, pos);
pushup(k);
}
int query1(int k, int l, int r) {
// write(k), putchar(' '), write(l), putchar(' '), write(r), puts("");
if (l <= c[k].l && c[k].r <= r) return c[k].h1;
int mid = c[k].l + c[k].r >> 1;
if (r <= mid) return query1(ls, l, r);
if (l > mid) return query1(rs, l, r);
return query1(ls, l, mid) * b[r - mid] % mod + query1(rs, mid + 1, r);
}
int query2(int k, int l, int r) {
if (l <= c[k].l && c[k].r <= r) return c[k].h2;
int mid = c[k].l + c[k].r >> 1;
if (r <= mid) return query2(ls, l, r);
if (l > mid) return query2(rs, l, r);
return query2(rs, mid + 1, r) * b[mid - l + 1] % mod + query2(ls, l, mid);
}
void Main() {
n = read();
b[0] = 1;
for (int i = 1; i <= n; ++i) b[i] = b[i - 1] * base % mod;
for (int i = 1; i <= n; ++i) a[i] = read();
build(1, 1, n);
// for (int i = 1; i <= n; ++i) modify(1, i);
// write(query1(1, 2, 5)), puts("");
for (int i = 1, l, r, h1, h2; i <= n; ++i) {
modify(1, a[i]);
l = std::max(1ll, a[i] * 2 - n);
r = std::min(n, a[i] * 2 - 1);
// write(a[i]), putchar(' '), write(l), putchar(' '), write(r), puts("");
if (a[i] == 1 || a[i] == n) continue;
// write(l), putchar(' '), write(a[i] - 1), putchar(' '), write(a[i] + 1), putchar(' '), write(r), puts("");
h1 = query1(1, l, a[i] - 1), h2 = query2(1, a[i] + 1, r);
// write(h1), putchar(' '), write(h2), puts("");
if (h1 != h2) {
puts("Y");
return;
}
}
puts("N");
}
signed main() {
int T = read();
while (T--) Main();
return 0;
}
/*
1
10
1 9 5 3 7 4 8 10 2 6
*/