[CEOI2014] Cake

CEOI2014 Day2 T2，译者：小粉兔

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

第一行两个正整数 $n, a$，分别表示蛋糕总块数以及 Leopold 第一次会吃掉哪一块蛋糕。 第二行 $n$ 个互不相同的正整数 $d_1, d_2, \ldots , d_n$，表示蛋糕的初始美丽度。 第三行一个正整数 $q$，表示操作的个数。 接下来 $q$ 行，每行形如 `E i e` 或 `F b` 表示一次操作： - `E i e`：将编号为 $i$ 的蛋糕的美味度提升至第 $e$ 美味的。保证在操作之前比编号为 $i$ 的蛋糕美味的蛋糕的数量至少为 $e$。 - `F b`：询问 Leopold 在吃掉编号为 $b$ 的蛋糕之前会吃掉多少块蛋糕。

对于每个 `F` 操作，输出一行一个数表示答案。

5 3
5 1 2 4 3
17
F 1
F 2
F 3
F 4
F 5
E 2 1
F 1
F 2
F 3
F 4
F 5
E 5 2
F 1
F 2
F 3
F 4
F 5

4
1
0
2
3
4
3
0
1
2
4
3
0
1
2

**【样例解释】** 在第一次增加美味度之前，编号为 $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$ | 无特殊限制 |