CF1404C Fixed Point Removal

给定一个长度为 $n$ 的正整数数组 $a_1, \ldots, a_n$。每次操作，你可以选择一个下标 $i$，使得 $a_i = i$，并将 $a_i$ 从数组中移除（移除后，剩余部分会自动拼接）。 数组 $a$ 的“权重”定义为你最多可以移除的元素数量。 你需要回答 $q$ 个独立的询问 $(x, y)$：将 $a$ 的前 $x$ 个元素和后 $y$ 个元素都替换为 $n+1$（使它们无法被移除）后，$a$ 的权重是多少？

第一行包含两个整数 $n$ 和 $q$（$1 \le n, q \le 3 \cdot 10^5$），分别表示数组的长度和询问的数量。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq n$），表示数组的元素。 接下来的 $q$ 行，每行包含两个整数 $x$ 和 $y$（$x, y \ge 0$ 且 $x + y < n$）。

输出 $q$ 行，第 $i$ 行输出第 $i$ 个询问的答案，即数组的权重。

对第一个询问的解释： 将前 $x = 3$ 个和后 $y = 1$ 个元素替换为无法移除后，$a$ 变为 $[\times, \times, \times, 9, 5, 4, 6, 5, 7, 8, 3, 11, \times]$（为方便起见，用 $\times$ 表示 $14$）。 以下是一种可以移除 $5$ 个元素的策略（被移除的元素用红色表示）： - $[\times, \times, \times, 9, \color{red}{5}, 4, 6, 5, 7, 8, 3, 11, \times]$ - $[\times, \times, \times, 9, 4, 6, 5, 7, 8, 3, \color{red}{11}, \times]$ - $[\times, \times, \times, 9, 4, \color{red}{6}, 5, 7, 8, 3, \times]$ - $[\times, \times, \times, 9, 4, 5, 7, \color{red}{8}, 3, \times]$ - $[\times, \times, \times, 9, 4, 5, \color{red}{7}, 3, \times]$ - $[\times, \times, \times, 9, 4, 5, 3, \times]$（最终状态） 无法移除超过 $5$ 个元素，因此权重为 $5$。 由 ChatGPT 4.1 翻译