← 返回题目列表

Codeforces · 279/C

C. 梯子

中文机器翻译题面 查看原题

你有一个数组,由 n 个整数 a1, a2, ..., an 组成。另外,你有 m 个查询,第 i 个查询由两个整数 li 和 ri 描述。数字 li, ri 定义了原始数组的子段,即数字序列 ali, ali + 1, ali + 2, ..., ari。对于每个查询,您应该检查相应的段是否是梯子。

阶梯是整数 b1, b2, ..., bk 的序列,它首先不减少,然后不增加。换句话说,存在这样的整数x (1 ≤ x ≤ k),满足以下不等式:b1 ≤ b2 ≤ ... ≤ bx ≥ bx + 1 ≥ bx + 2 ... ≥ bk。请注意,非递减和非递增序列也被视为梯子。

输入

第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 105) — 数组元素的数量和查询的数量。第二行包含整数序列 a1, a2, ..., an (1 ≤ ai ≤ 109),其中数字 ai 代表第 i 个数组元素。

以下 m 行包含查询的描述。第 i 行包含第 i 个查询的描述,由两个整数 li, ri (1 ≤ li ≤ ri ≤ n) 组成 - 初始数组的子段的边界。

行中的数字由单个空格分隔。

输出

打印 m 行,如果第 i 个查询对应的子段是梯形图,则在第 i 行打印单词“Yes”(不带引号),否则打印单词“No”(不带引号)。

示例

输入 #1

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

输出 #1

Yes
Yes
No
Yes
No
Yes