← 返回题目列表

Codeforces · 1887/D

D. 分裂

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

如果可以将数组 $$$b_1, b_2, \ldots, b_m$$$ ($$$m \ge 2$$$) 分成两部分,使得左侧部分中的所有元素都严格小于右侧部分中的所有元素,我们称其为良好。换句话说,必须存在一个索引 $$$1 \le i < m$$$,使得 $$$b_1, \ldots, b_i$$$ 中的每个元素都严格小于 $$$b_{i+1}, \ldots, b_m$$$ 中的每个元素。

给定一个数组 $$$a_1, a_2, \ldots a_n$$$,由从 $$$1$$$ 到 $$$n$$$ 的不同整数组成。有 $$$q$$$ 查询。每个查询由两个数字 $$$l$$$ 和 $$$r$$$ 组成。对于每个查询,确定数组 $$$a_l, a_{l+1}, \ldots, a_r$$$ 是否良好。

输入

第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$) — 数组的大小。

第二行包含 $$$n$$$ 不同的整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_n \le n$$$) — 数组 $$$a$$$ 的元素。

第三行包含一个整数 $$$q$$$ ($$$1 \le q \le 3 \cdot 10^5$$$) — 查询数。

接下来的 $$$q$$$ 行包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$1 \le l_i < r_i \le n$$$) — 第 $$$i$$$ 查询的描述。

输出

对于每个查询,如果数组 $$$a_l, a_{l+1}, \ldots, a_r$$$ 良好,则输出“Yes”(不带引号),否则输出“No”(不带引号)。

在任何情况下都可以输出“Yes”和“No”(例如,字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定答案)。

示例

输入 #1

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

输出 #1

Yes
No
Yes
No
Yes

输入 #2

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

输出 #2

Yes
No
Yes

注意

在第一个示例中:

- 数组 $$$[3,2,1,4,5]$$$ 可以分为两部分:$$$[3,2,1]$$$ 和 $$$[4,5]$$$。
- 数组 $$$[3,2,1]$$$ 无法拆分为两部分,使得左侧部分中的所有元素都小于右侧部分中的所有元素。
- 数组 $$$[3,2,1,4]$$$ 可以分为两部分:$$$[3,2,1]$$$ 和 $$$[4]$$$。
- 数组 $$$[3,2]$$$ 无法拆分为两部分,使得左侧部分中的所有元素都小于右侧部分中的所有元素。
- 数组 $$$[2,1,4,5]$$$ 可以分为两部分:$$$[2,1]$$$ 和 $$$[4,5]$$$。

在第二个示例中:

- 数组 $$$[2,4,3]$$$ 可以分为两部分:$$$[2]$$$ 和 $$$[4,3]$$$。
- 数组 $$$[6,2,4,3,5]$$$ 不能分成两部分,使得左侧部分中的所有元素都小于右侧部分中的所有元素。
- 数组 $$$[4,3,5]$$$ 可以分为两部分:$$$[4,3]$$$ 和 $$$[5]$$$。