#P17871. [Ontak2019]PER

    ID: 16811 传统题 500~5000ms 256MiB 尝试: 1 已通过: 1 难度: 7 上传者: 标签>动态规划排序与序列处理单调队列数据结构CF2300

[Ontak2019]PER

— 排列分段

给定一个正整数序列。判断能否把整个序列划分成若干个非空连续段,使每一段都是一个排列。各段长度可以不同。

长度为 kk 的排列恰好包含整数 1,2,…,k1,2,\ldots,k,每个出现一次。

输入格式

第一行一个整数 zz,表示测试用例数。

接下来 zz 行,每行先给出一个整数 nn,然后给出序列的 nn 个元素。

输出格式

每个测试用例输出一行:能够划分时输出 YES,否则输出 NO。

数据范围

1≤z≤1001\le z\le100,1≤n≤1061\le n\le10^6,1≤ai≤1091\le a_i\le10^9。同一输入文件中所有序列的长度之和不超过 10710^7。

子任务 附加限制 分值
1 n≤100n\le100 20
2 n≤2000n\le2000 25
3 无 55

样例 1

输入:

4
1 1
1 2
6 1 2 3 1 2 3
5 1 3 2 3 1

输出:

YES
NO
YES
NO