CF1887D.Split

我们称一个数组 $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$ 中的每个元素。

给定一个由 $1$ 到 $n$ 的 $n$ 个互不相同的整数构成的数组 $a_1, a_2, \ldots, a_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_i \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" 都会被识别为正答）。

在第一个样例中：

• 数组 $[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]$。

由 ChatGPT 4.1 翻译