[CEOI 2014] Cake

时间限制:20s      空间限制:1024MB

题目描述

Leopold买了n块蛋糕, 这些蛋糕排成一排,从左到右记为1到n,第i块蛋糕最初的美味度为di。
Leopold每次固定最先吃第k块蛋糕,于是位置k就空出来了。之后他吃的每一块蛋糕总是位于某个空的位置旁边,并且是美味度最低的一块。因此在任何时刻,所有空的位置是一段连续的区间。Leopold会装饰自己的蛋糕来增加它的美味度,被加过装饰的蛋糕一定会成为最美味的10个蛋糕之一,任何时候都不存在两块美味度相同的蛋糕。
Leopold想知道在他吃到某块蛋糕b之前需要吃掉多少块蛋糕。
 


输入格式

第一行两个整数n和k,表示蛋糕的数量和Leopold吃的第一块蛋糕的位置。
第二行n个不同的整数d1,d2...,dn,表示第i块蛋糕最初的美味度。
第三行一个整数q,表示操作的数量。
下面q行会包括以下两种操作。
(1)E i e 蛋糕i被装饰成了第e美味的蛋糕(即原来前e-1美味的蛋糕不变,原来第e美味的蛋糕变成了第e+1美味的蛋糕,以此类推)注意每次装饰一定会增加美味度。
(2)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被吃掉。但装饰以后,由于蛋糕2美味度较高,它不会很快被吃掉,而蛋糕4和5会先被吃掉。但是第二次对蛋糕5的装饰对于吃掉蛋糕的顺序没有影响。
 
对于100%的数据满足
1≤k≤n≤250000
1≤q≤500000
1≤e≤10


题目来源

uploaded by dwellings