#P17989. Good Permutations

Good Permutations

Good Permutations

题目描述

一个长度为 kk 的序列 pp 是好排列,当且仅当它是 1,2,…,k1,2,\ldots,k 的一个排列,并且对每个 1≤i<k1\le i<k 都有

pi+1≥pi−1.p_{i+1}\ge p_i-1.

给定长度为 nn 的数组 aa,每个元素是 −1-1 或 11 到 nn 之间的整数。回答 qq 个相互独立的查询 (l,r)(l,r):能否将子数组 al,…,ara_l,\ldots,a_r 中的所有 −1-1 替换为正整数,使这个子数组成为好排列?原本不等于 −1-1 的元素不能更改。

输入格式

第一行两个整数 n,qn,q。第二行 nn 个整数 a1,…,ana_1,\ldots,a_n。

接下来 qq 行,每行两个整数 li,ril_i,r_i,表示查询区间。

输出格式

输出 qq 行,每行 YES 或 NO,依次表示对应查询是否可行。

数据范围

1≤n,q≤2×1051\le n,q\le2\times10^5,ai∈{−1,1,2,…,n}a_i\in\{-1,1,2,\ldots,n\},1≤li≤ri≤n1\le l_i\le r_i\le n。

样例 1 输入

5 3
-1 2 1 -1 5
1 5
2 5
2 4

样例 1 输出

YES
NO
YES

第一组查询可以得到 (3,2,1,4,5)(3,2,1,4,5)。第二组的长度为 44,不能含值 55。第三组可以得到 (2,1,3)(2,1,3)。

样例 2 输入

2 2
1 1
1 2
1 1

样例 2 输出

NO
YES