Description

给一个 \(1\) 到 \(n\) 的排列 \(\{A_i\}\), 询问是否存在 \(p_1, p_2, p_3\), 使得 \(A_{p_1}, A_{p_2}, A_{p_3}\) 是一个等差序列.

Input

输入的第一行包含一个整数 \(T\), 表示组数.

下接 \(T\) 组数据, 每组第一行一个整数 \(n\), 每组第二行为一个 \(1\) 到 \(n\) 的排列, 数字两两之间用空格隔开.

Output

对于每组数据, 如果存在一个等差子序列, 则输出一行 Y, 否则输出一行 N.

Sample Input

2
3
1 3 2
3
3 2 1

Sample Output

N
Y

Data Range

对于 100% 的数据,\(n \leq 10000, T \leq 7\)

Explanation

题目就是求是否存在 \(i \lt j \lt k\), 使得 \(A_k - A_j = A_j - A_i\).

我们不妨枚举中间那个数为 \(x\), 然后按照输入的顺序对 \(x\) 进行操作. 如果 \(x\) 满足 条件, 也就是存在两个数 \(y\) 和 \(z\),\(x - y = z - x\), 并且 \(y\) 已经出现过了而 \(z\) 还没有出现, 那么我们就可以直接输出 Y 了.

然后用一个奇怪的 mod 哈希维护一下基本就过了.

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>

using namespace std;
typedef long long lli;
const int maxn = 10010;
const lli modr = 1000000007;

lli pwr[maxn];
class BinaryIndexedTree
{
public:
    lli data[maxn];
    int n;
    void change(int x) {
        for (int i = x; i <= n; i += i & -i)
            data[i] = (data[i] + pwr[i - x]) % modr;
        return ;
    }
    lli query_raw(int x) {
        lli res = 0;
        for (int i = x; i > 0; i ^= i & -i)
            res = (data[i] * pwr[x - i] + res) % modr;
        return res;
    }
    int query(int x, int y) {
        lli p = query_raw(x-1),
            q = query_raw(y);
        return (q - p * pwr[y-x+1] % modr + modr) % modr;
    }
    void init(int n) {
        this->n = n;
        memset(data, 0, sizeof(data));
        return ;
    }
} bit1, bit2;

int cases, n, arr[maxn];

int main(int argc, char** argv)
{
    // String hashes
    pwr[0] = 1;
    for (int i = 1; i <= 10000; i++)
        pwr[i] = pwr[i - 1] * 12347 % modr;
    // Reading cases
    scanf("%d", &cases);
    for (int idx = 1; idx <= cases; idx++) {
        scanf("%d", &n);
        bit1.init(n);
        bit2.init(n);
        for (int i = 1; i <= n; i++)
            scanf("%d", &arr[i]);
        // Whether to query?
        int i = 1;
        for (; i <= n; i++) {
            int x = min(arr[i] - 1, n - arr[i]);
            if (x && bit1.query(arr[i] - x, arr[i] - 1)
                != bit2.query(n - arr[i] - x + 1, n - arr[i]))
                break;
            bit1.change(arr[i]);
            bit2.change(n - arr[i] + 1);
        }
        printf("%s\n", i > n ? "N" : "Y");
    }
    return 0;
}