问题2028--魔兽争霸(war)

2028: 魔兽争霸(war)

时间限制: 1 Sec  内存限制: 128 MB
提交: 4  解决: 2
[提交] [状态] [讨论版] [命题人:]

题目描述

小x正在销魂地玩魔兽
他正控制着死亡骑士和n个食尸鬼(编号1~n)去打猎
死亡骑士有个魔法,叫做“死亡缠绕”,可以给食尸鬼补充HP
战斗过程中敌人会对食尸鬼实施攻击,食尸鬼的HP会减少
小x希望随时知道自己部队的情况,即HP值第k多的食尸鬼有多少HP,以便决定如何施放魔法
请同学们帮助他:)
小x向你发出3种信号:(下划线在输入数据中表现为空格)
A_i_a  表示敌军向第i个食尸鬼发出了攻击,并使第i个食尸鬼损失了a点HP,如果它的HP<=0,那么这个食尸鬼就死了(Undead也是要死的„„)。
敌军不会攻击一个已死的食尸鬼。
C_i_a  表示死亡骑士向第i个食尸鬼放出了死亡缠绕,并使其增加了a点HP。
HP值没有上限。
死亡骑士不会向一个已死的食尸鬼发出死亡缠绕
Q_k  表示小x向你发出询问

输入

第一行,一个正整数 n
以后n个整数 表示n个食尸鬼的初始HP值
接着一个正整数m
以下m行 每行一个小x发出的信号

输出

对于小x的每个询问,输出HP第k多的食尸鬼有多少HP,如果食尸鬼总数不足k个,输出-1。每个一行数。
最后一行输出一个数:战斗结束后剩余的食尸鬼数

样例输入 Copy

5
1 2 3
4 5
10
Q 2
A 4 6
C 1 4
Q 2
A 2 1
A 3 3
A 1 3
Q 4
C 2 10
Q 1

样例输出 Copy

4
5
-1
11
3

提示

40%的数据 n<=3000 m<=5000
70%的数据 n<=8000 m<=10000
100%的数据 n<=30000 m<=50000
90%的数据随机生成
食尸鬼HP没有上限
数据保证任意时刻食尸鬼的HP值在longint范围内
数据保证A和C命令中的食尸鬼是活着的
输入数据中没有多余空格、换行