{"problem":{"name":"[ROIR 2023] 石头 (Day 2)","description":{"content":"Bob 面前排列着 $n$ 个黑色石头，从 $1$ 到 $n$ 编号。第 $i$ 个石头上写有一个整数 $a_i$，$n$ 个石头上写的整数构成了一个排列。我们称第 $i$ 个石头的相邻石头为第 $(i-1)$ 个和第 $(i+1)$ 个石头（如果存在的话）。 Bob 按照以下步骤进行 $n$ 次操作： - 在第一步，选择任意的 $i$（$1\\le i\\le n$），并将第 $i$ 个石头涂成","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10100"},"statements":[{"statement_type":"Markdown","content":"Bob 面前排列着 $n$ 个黑色石头，从 $1$ 到 $n$ 编号。第 $i$ 个石头上写有一个整数 $a_i$，$n$ 个石头上写的整数构成了一个排列。我们称第 $i$ 个石头的相邻石头为第 $(i-1)$ 个和第 $(i+1)$ 个石头（如果存在的话）。\n\nBob 按照以下步骤进行 $n$ 次操作：\n\n- 在第一步，选择任意的 $i$（$1\\le i\\le n$），并将第 $i$ 个石头涂成白色。\n- 在第 $2$ 到第 $n$ 步，选取相邻石头中至少有一个白色石头的黑色石头中的 $a_i$ 最小的石头 $j$（即，可能有很多个黑色石头满足它的相邻石头中至少有一个白色石头，但是要选取其中 $a_i$ 最小的那个），并将其涂成白色。\n\n很容易看出，在执行完所有步骤后，$n$ 个石头都是白色的。\n\nAlice 选择了 $q$ 对值 $p_j$ 和 $k_j$。对于每对 $p$ 和 $k$ 的值，她想知道有多少种不同的选择第一步时将哪块石头涂成白色的方式，使得第 $p$ 块石头在第 $k$ 步变成白色。\n\n帮助 Bob 回答 Alice 的 $q$ 个查询。\n\n## Input\n\n第一行包含两个整数 $n$ 和 $q$，分别表示石头的数量和查询的数量。\n\n第二行包含 $n$ 个整数 $a_1,a_2,\\dots,a_n$，表示写在石头上的整数。\n\n接下来的 $q$ 行，每行包含一对整数 $p_j$ 和 $k_j$。\n\n## Output\n\n对于每个查询，输出一个整数，表示查询的答案。\n\n[samples]\n\n## Background\n\n翻译自 [ROIR 2023 D2T3](https://neerc.ifmo.ru/school/archive/2022-2023/ru-olymp-regional-2023-day2.pdf)。\n\n## Note\n\n下面的样例解释中加粗的数是被涂成白色的。\n\n在第一个样例中：\n\n- 如果第一步选择第 $1$ 块石头：\n  - 第 $1$ 步：$[\\bold1, \\gray4, \\gray6, \\gray5, \\gray2, \\gray3]$；\n  - 第 $2$ 步：$[\\bold1, \\bold4, \\gray6, \\gray5, \\gray2, \\gray3]$；\n  - 第 $3$ 步：$[\\bold1, \\bold4, \\bold6, \\gray5, \\gray2, \\gray3]$；\n  - 第 $4$ 步：$[\\bold1, \\bold4, \\bold6, \\bold5, \\gray2, \\gray3]$；\n  - 第 $5$ 步：$[\\bold1, \\bold4, \\bold6, \\bold5, \\bold2, \\gray3]$；\n  - 第 $6$ 步：$[\\bold1, \\bold4, \\bold6, \\bold5, \\bold2, \\bold3]$。\n- 如果第一步选择第 $2$ 块石头：\n  - 第 $1$ 步：$[\\gray1, \\bold4, \\gray6, \\gray5, \\gray2, \\gray3]$；\n  - 第 $2$ 步：$[\\bold1, \\bold4, \\gray6, \\gray5, \\gray2, \\gray3]$；\n  - 第 $3$ 步：$[\\bold1, \\bold4, \\bold6, \\gray5, \\gray2, \\gray3]$；\n  - 第 $4$ 步：$[\\bold1, \\bold4, \\bold6, \\bold5, \\gray2, \\gray3]$；\n  - 第 $5$ 步：$[\\bold1, \\bold4, \\bold6, \\bold5, \\bold2, \\gray3]$；\n  - 第 $6$ 步：$[\\bold1, \\bold4, \\bold6, \\bold5, \\bold2, \\bold3]$。\n- 如果第一步选择第 $3$ 块石头：\n  - 第 $1$ 步：$[\\gray1, \\gray4, \\bold6, \\gray5, \\gray2, \\gray3]$；\n  - 第 $2$ 步：$[\\gray1, \\bold4, \\bold6, \\gray5, \\gray2, \\gray3]$；\n  - 第 $3$ 步：$[\\bold1, \\bold4, \\bold6, \\gray5, \\gray2, \\gray3]$；\n  - 第 $4$ 步：$[\\bold1, \\bold4, \\bold6, \\bold5, \\gray2, \\gray3]$；\n  - 第 $5$ 步：$[\\bold1, \\bold4, \\bold6, \\bold5, \\bold2, \\gray3]$；\n  - 第 $6$ 步：$[\\bold1, \\bold4, \\bold6, \\bold5, \\bold2, \\bold3]$。\n- 如果第一步选择第 $4$ 块石头：\n  - 第 $1$ 步：$[\\gray1, \\gray4, \\gray6, \\bold5, \\gray2, \\gray3]$；\n  - 第 $2$ 步：$[\\gray1, \\gray4, \\gray6, \\bold5, \\bold2, \\gray3]$；\n  - 第 $3$ 步：$[\\gray1, \\gray4, \\gray6, \\bold5, \\bold2, \\bold3]$；\n  - 第 $4$ 步：$[\\gray1, \\gray4, \\bold6, \\bold5, \\bold2, \\bold3]$；\n  - 第 $5$ 步：$[\\gray1, \\bold4, \\bold6, \\bold5, \\bold2, \\bold3]$；\n  - 第 $6$ 步：$[\\bold1, \\bold4, \\bold6, \\bold5, \\bold2, \\bold3]$。\n- 如果第一步选择第 $5$ 块石头：\n  - 第 $1$ 步：$[\\gray1, \\gray4, \\gray6, \\gray5, \\bold2, \\gray3]$；\n  - 第 $2$ 步：$[\\gray1, \\gray4, \\gray6, \\gray5, \\bold2, \\bold3]$；\n  - 第 $3$ 步：$[\\gray1, \\gray4, \\gray6, \\bold5, \\bold2, \\bold3]$；\n  - 第 $4$ 步：$[\\gray1, \\gray4, \\bold6, \\bold5, \\bold2, \\bold3]$；\n  - 第 $5$ 步：$[\\gray1, \\bold4, \\bold6, \\bold5, \\bold2, \\bold3]$；\n  - 第 $6$ 步：$[\\bold1, \\bold4, \\bold6, \\bold5, \\bold2, \\bold3]$。\n- 如果第一步选择第 $6$ 块石头：\n  - 第 $1$ 步：$[\\gray1, \\gray4, \\gray6, \\gray5, \\gray2, \\bold3]$；\n  - 第 $2$ 步：$[\\gray1, \\gray4, \\gray6, \\gray5, \\bold2, \\bold3]$；\n  - 第 $3$ 步：$[\\gray1, \\gray4, \\gray6, \\bold5, \\bold2, \\bold3]$；\n  - 第 $4$ 步：$[\\gray1, \\gray4, \\bold6, \\bold5, \\bold2, \\bold3]$；\n  - 第 $5$ 步：$[\\gray1, \\bold4, \\bold6, \\bold5, \\bold2, \\bold3]$；\n  - 第 $6$ 步：$[\\bold1, \\bold4, \\bold6, \\bold5, \\bold2, \\bold3]$。\n\n本题使用捆绑测试。\n\n| 子任务编号 | 分值 | 特殊性质 |\n| :----------: | :----------: | :----------: |\n| $1$ | $20$ | $n,q\\le300$ |\n| $2$ | $17$ | $n\\le3000$ |\n| $3$ | $12$ | $n\\le50000,q\\le10$ |\n| $4$ | $6$ | $a_i$ 的值递增 |\n| $5$ | $16$ | 所有 $k_i$ 相等 |\n| $6$ | $15$ | 所有 $p_i$ 相等 |\n| $7$ | $14$ | 无特殊性质 |\n\n对于 $100\\%$ 的数据，$2 \\le n \\le 10^5$，$1 \\le q \\le 10^5$，$1 \\le a_i \\le n$ 且所有 $a_i$ 互不相同，$1 \\le p_j,k_j \\le n$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10100","tags":["2023","ROIR（俄罗斯）"],"sample_group":[["6 4\n1 4 6 5 2 3\n3 1\n2 2\n6 3\n4 3","1\n2\n1\n2"],["5 3\n5 2 3 4 1\n2 3\n4 4\n3 2","0\n1\n1"]],"created_at":"2026-03-03 11:09:25"}}