English · Original
Chinese · Translation
Formal · Original
Vladik had started reading a complicated book about algorithms containing _n_ pages. To improve understanding of what is written, his friends advised him to read pages in some order given by permutation _P_ = \[_p_1, _p_2, ..., _p__n_\], where _p__i_ denotes the number of page that should be read _i_\-th in turn.
Sometimes Vladik’s mom sorted some subsegment of permutation _P_ from position _l_ to position _r_ inclusive, because she loves the order. For every of such sorting Vladik knows number _x_ — what index of page in permutation he should read. He is wondered if the page, which he will read after sorting, has changed. In other words, has _p__x_ changed? After every sorting Vladik return permutation to initial state, so you can assume that each sorting is independent from each other.
## Input
First line contains two space-separated integers _n_, _m_ (1 ≤ _n_, _m_ ≤ 104) — length of permutation and number of times Vladik's mom sorted some subsegment of the book.
Second line contains _n_ space-separated integers _p_1, _p_2, ..., _p__n_ (1 ≤ _p__i_ ≤ _n_) — permutation _P_. Note that elements in permutation are distinct.
Each of the next _m_ lines contains three space-separated integers _l__i_, _r__i_, _x__i_ (1 ≤ _l__i_ ≤ _x__i_ ≤ _r__i_ ≤ _n_) — left and right borders of sorted subsegment in _i_\-th sorting and position that is interesting to Vladik.
## Output
For each mom’s sorting on it’s own line print "_Yes_", if page which is interesting to Vladik hasn't changed, or "_No_" otherwise.
[samples]
## Note
Explanation of first test case:
1. \[1, 2, 3, 4, 5\] — permutation after sorting, 3\-rd element hasn’t changed, so answer is "_Yes_".
2. \[3, 4, 5, 2, 1\] — permutation after sorting, 1\-st element has changed, so answer is "_No_".
3. \[5, 2, 3, 4, 1\] — permutation after sorting, 3\-rd element hasn’t changed, so answer is "_Yes_".
4. \[5, 4, 3, 2, 1\] — permutation after sorting, 4\-th element hasn’t changed, so answer is "_Yes_".
5. \[5, 1, 2, 3, 4\] — permutation after sorting, 3\-rd element has changed, so answer is "_No_".
Vladik 开始阅读一本包含 $n$ 页的复杂算法书。为了更好地理解内容，他的朋友们建议他按照排列 $P = [p_1, p_2, \dots, p_n]$ 的顺序阅读页面，其中 $p_i$ 表示第 $i$ 个阅读的页面编号。
有时，Vladik 的妈妈会将排列 $P$ 中从位置 $l$ 到位置 $r$（包含）的子段进行排序，因为她喜欢有序。对于每一次这样的排序，Vladik 知道一个数 $x$ —— 他需要阅读的页面在排列中的索引。他想知道，经过排序后，他要阅读的页面是否发生了变化。换句话说，$p_x$ 是否发生了变化？每次排序后，Vladik 都会将排列恢复为初始状态，因此你可以假设每次排序是相互独立的。
第一行包含两个用空格分隔的整数 $n$, $m$ ($1 \leq n, m \leq 10^4$) —— 排列的长度和 Vladik 的妈妈对书的子段进行排序的次数。
第二行包含 $n$ 个用空格分隔的整数 $p_1, p_2, \dots, p_n$ ($1 \leq p_i \leq n$) —— 排列 $P$。注意排列中的元素互不相同。
接下来的 $m$ 行中，每行包含三个用空格分隔的整数 $l_i$, $r_i$, $x_i$ ($1 \leq l_i \leq x_i \leq r_i \leq n$) —— 第 $i$ 次排序的子段左右边界和 Vladik 感兴趣的位置。
对于每次妈妈的排序，请在单独的一行输出 "_Yes_"，如果 Vladik 感兴趣的页面没有变化；否则输出 "_No_"。
第一个测试用例的解释：
## Input
第一行包含两个用空格分隔的整数 $n$, $m$ ($1 \leq n, m \leq 10^4$) —— 排列的长度和 Vladik 的妈妈对书的子段进行排序的次数。第二行包含 $n$ 个用空格分隔的整数 $p_1, p_2, \dots, p_n$ ($1 \leq p_i \leq n$) —— 排列 $P$。注意排列中的元素互不相同。每行接下来的 $m$ 行包含三个用空格分隔的整数 $l_i$, $r_i$, $x_i$ ($1 \leq l_i \leq x_i \leq r_i \leq n$) —— 第 $i$ 次排序的子段左右边界和 Vladik 感兴趣的位置。
## Output
对于每次妈妈的排序，请在单独的一行输出 "_Yes_"，如果 Vladik 感兴趣的页面没有变化；否则输出 "_No_"。
[samples]
## Note
第一个测试用例的解释：
$[1, 2, 3, 4, 5]$ —— 排序后的排列，第 $3$ 个元素没有变化，因此答案为 "_Yes_"。
$[3, 4, 5, 2, 1]$ —— 排序后的排列，第 $1$ 个元素发生了变化，因此答案为 "_No_"。
$[5, 2, 3, 4, 1]$ —— 排序后的排列，第 $3$ 个元素没有变化，因此答案为 "_Yes_"。
$[5, 4, 3, 2, 1]$ —— 排序后的排列，第 $4$ 个元素没有变化，因此答案为 "_Yes_"。
$[5, 1, 2, 3, 4]$ —— 排序后的排列，第 $3$ 个元素发生了变化，因此答案为 "_No_"。
**Definitions:**
- Let $ P = [p_1, p_2, \dots, p_n] $ be a permutation of $ \{1, 2, \dots, n\} $.
- For each query $ i $, given $ (l_i, r_i, x_i) $, let $ Q $ be the permutation obtained by sorting the subsegment $ P[l_i:r_i] $ (inclusive) in non-decreasing order, while leaving the rest of $ P $ unchanged.
**Given:**
- $ n, m \in \mathbb{N} $, $ 1 \leq n, m \leq 10^4 $
- $ P \in S_n $, a permutation of $ \{1, 2, \dots, n\} $
- $ m $ queries, each of the form $ (l, r, x) $, with $ 1 \leq l \leq x \leq r \leq n $
**Objective:**
For each query $ (l, r, x) $, determine whether $ p_x $ remains at position $ x $ after sorting the subsegment $ P[l:r] $.
That is, let $ P' $ be the permutation where:
- $ P'[j] = P[j] $ for $ j \notin [l, r] $
- $ P'[l:r] $ is the sorted (ascending) version of $ P[l:r] $
Then output:
- "Yes" if $ P'[x] = P[x] $
- "No" otherwise
**Equivalent Condition:**
Let $ S = \{ p_j \mid l \leq j \leq r \} $ be the multiset of values in the subsegment.
Let $ k $ be the number of elements in $ S $ that are **strictly less than** $ p_x $.
Then $ P'[x] = P[x] $ **if and only if** the rank of $ p_x $ within $ S $ (i.e., its position in the sorted version of $ S $) places it exactly at position $ x $ in the original array.
More precisely:
After sorting $ P[l:r] $, the element $ p_x $ will be placed at position $ l + k $ in the new array (since $ k $ smaller elements come before it).
Thus, $ P'[x] = P[x] $ **iff**
$$
l + k = x
$$
Where $ k = \left| \{ j \in [l, r] \mid p_j < p_x \} \right| $
---
**Final Formal Statement:**
For each query $ (l, r, x) $:
Let $ k = \#\{ j \in [l, r] \mid p_j < p_x \} $
Then:
$$
\text{Answer} =
\begin{cases}
\text{"Yes"} & \text{if } l + k = x \\
\text{"No"} & \text{otherwise}
\end{cases}
$$
API Response (JSON)
{
"problem": {
"name": "B. Vladik and Complicated Book",
"description": {
"content": "Vladik had started reading a complicated book about algorithms containing _n_ pages. To improve understanding of what is written, his friends advised him to read pages in some order given by permutati",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF811B"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Vladik had started reading a complicated book about algorithms containing _n_ pages. To improve understanding of what is written, his friends advised him to read pages in some order given by permutati...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Vladik 开始阅读一本包含 $n$ 页的复杂算法书。为了更好地理解内容，他的朋友们建议他按照排列 $P = [p_1, p_2, \\dots, p_n]$ 的顺序阅读页面，其中 $p_i$ 表示第 $i$ 个阅读的页面编号。\n\n有时，Vladik 的妈妈会将排列 $P$ 中从位置 $l$ 到位置 $r$（包含）的子段进行排序，因为她喜欢有序。对于每一次这样的排序，Vladik 知道一个数 $x...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions:**\n\n- Let $ P = [p_1, p_2, \\dots, p_n] $ be a permutation of $ \\{1, 2, \\dots, n\\} $.\n- For each query $ i $, given $ (l_i, r_i, x_i) $, let $ Q $ be the permutation obtained by sorting t...",
"is_translate": false,
"language": "Formal"
}
]
}