P6544 [CEOI 2014] Cake

CEOI2014 Day2 T2，译者：小粉兔

Leopold 和 Molly 都喜欢蛋糕：Leopold 喜欢吃蛋糕，Molly 喜欢看 Leopold 吃蛋糕。 现在有 $n$ 块蛋糕排成一排，从左到右数的第 $i$ 块蛋糕编号为 $i$，每块蛋糕有一个美味度 $d_i$。 Leopold 会先吃掉编号为 $a$ 的蛋糕，这样位置 $a$ 就空了。接下来每次他会选择一个与空出的位置相邻的蛋糕中美味度最小的蛋糕吃掉（要把好吃的留到最后）。你可以发现空出的位置一定是一个连续的区间。 为了让事情更加有趣，Molly 有时会给某一块蛋糕上加一点装饰，以增加它的美味度。她保证做完此操作后，这块蛋糕的美味度会变成所有蛋糕中前 $10$ 大的。而且在任何时候任意两块蛋糕的美味度都不同。 有时 Molly 好奇在 Leopold 吃掉某块特定的编号为 $b$ 的蛋糕之前，他会吃掉多少块蛋糕。 请你帮助 Molly 编写一个程序，给出操作序列，回答 Molly 的询问。

无

无

**【样例解释】** 在第一次增加美味度之前，编号为 $3, 2, 4, 5, 1$ 的蛋糕会依次被吃掉。但接下来编号为 $1$ 的蛋糕太好吃了以至于它不会先被吃掉，编号为 $4$ 和 $5$ 的蛋糕先被吃掉了。注意最后一次对编号为 $5$ 的蛋糕的美味度的增加不会改变吃蛋糕的顺序。 **【数据范围与提示】** 对于所有数据，保证 $1 \le n \le 2.5 \times {10}^5$，$1 \le q \le 5 \times {10}^5$，$1 \le d_i, a, i, b \le n$，$1 \le e \le 10$。 | 子任务编号 | 分值 | 特殊限制 | | :-: | :-: | :-: | | $1$ | $15$ | $n, q \le {10}^4$ | | $2$ | $15$ | $n \le 2.5 \times {10}^4$ 且 `F` 操作的数量不超过 $500$ | | $3$ | $20$ | $q \le {10}^5$ 且 `E` 操作的数量不超过 $100$ | | $4$ | $50$ | 无特殊限制 |