信息學(xué)奧賽一本通T1567-郁悶的出納員
題目描述
原題來(lái)自：NOI 2004
OIER 公司是一家大型專(zhuān)業(yè)化軟件公司，有著數(shù)以萬(wàn)計(jì)的員工。作為一名出納員，我的任務(wù)之一便是統(tǒng)計(jì)每位員工的工資。這本來(lái)是一份不錯(cuò)的工作，但是令人郁悶的是，我們的老板反復(fù)無(wú)常，經(jīng)常調(diào)整員工的工資。如果他心情好，就可能把每位員工的工資加上一個(gè)相同的量。反之，如果心情不好，就可能把他們的工資扣除一個(gè)相同的量。我真不知道除了調(diào)工資他還做什么其它事情。
工資的頻繁調(diào)整很讓員工反感，尤其是集體扣除工資的時(shí)候。一旦某位員工發(fā)現(xiàn)自己的工資已經(jīng)低于了合同規(guī)定的工資下界，他就會(huì)立刻氣憤地離開(kāi)公司，并且再也不會(huì)回來(lái)了。每位員工的工資下界都是統(tǒng)一規(guī)定的。每當(dāng)一個(gè)人離開(kāi)公司，我就要從電腦中把他的工資檔案刪去，同樣，每當(dāng)公司招聘了一位新員工，我就得為他新建一個(gè)工資檔案。
老板經(jīng)常到我這邊來(lái)詢(xún)問(wèn)工資情況，他并不問(wèn)具體某位員工的工資情況，而是問(wèn)現(xiàn)在工資第 kk 多的員工拿多少工資。每當(dāng)這時(shí)，我就不得不對(duì)數(shù)萬(wàn)個(gè)員工進(jìn)行一次漫長(zhǎng)的排序，然后告訴他答案。
好了，現(xiàn)在你已經(jīng)對(duì)我的工作了解不少了。正如你猜的那樣，我想請(qǐng)你編一個(gè)工資統(tǒng)計(jì)程序。怎么樣，不是很困難吧？
輸入格式
接下來(lái)的 n 行，每行表示一個(gè)命令。命令可以是以下四種之一：
I 命令，A 命令，S 命令中，k 是一個(gè)非負(fù)整數(shù)。F 命令中，k 是一個(gè)正整數(shù)。
在初始時(shí)，可以認(rèn)為公司中一位員工也沒(méi)有。
輸出格式
對(duì)于每條 F 命令，你的程序要輸出一行，僅包含一個(gè)整數(shù)，為當(dāng)前工資第 k 多的員工所拿的工資數(shù)，如果 k 大于目前員工的數(shù)目，則輸出 ?1；
輸出的最后一行包含一個(gè)整數(shù)，為離開(kāi)公司的員工的總數(shù)（不包括因員工的初始工資低于工資下界而離開(kāi)公司的情況）。
樣例輸入
9 10 I 60 I 70 S 50 F 2 I 30 S 15 A 5 F 1 F 2
樣例輸出
10 20 -1 2
提示
對(duì)于全部數(shù)據(jù)，I命令的條數(shù)不超過(guò) 105 ，A 命令和 S 命令的總條數(shù)不超過(guò) 100，F(xiàn) 命令的條數(shù)不超過(guò) 105 。
每次工資調(diào)整的調(diào)整量不超過(guò) 103 ，新員工的工資不超過(guò) 105 。