King Kog's Reception

题意翻译

国王Kog由于他的骑士的散漫而恼火：他们可以不提前通知闯入他的大厅！因此，国王决定建造一个要排队的接待处，在那里每个骑士提前选择他要来拜访的时刻和拜访将持续的时间。骑士按照接待处记录的拜访时刻顺序依次服务国王，但每个骑士必须等前面的骑士结束拜访。 公主Keabeanie想要见她的父亲，但她不想打乱骑士们所以她排进了队。不幸的是，骑士们经常改变主意，他们可以排进队或取消拜访。如果公主在特殊的时间排进队并在接待处留下了记录，请帮助公主弄明白她要等多久才能见到她的父亲。 输入格式： 第一行一个正整数q(1<=q<=300000)，表示事件个数。每个事件可以是加入、取消或查询 **加入** "+ t d" (1<=t,d<=10^6)：t表示新骑士加入的时刻，d表示这名骑士的拜访将持续的时间 **取消** "-i" (1<=i<=q) 骑士取消了拜访，i代表所有事件中“加入”事件的次序（从1开始计算） **查询** "? t" (1<=t<=10^6) Keabeanie询问如果她在时刻t到来，她要等多久 输出格式： 对每一个查询操作输出一行，即Keabeanie需要等待的时间

题目描述

King Kog got annoyed of the usual laxity of his knights — they can break into his hall without prior notice! Thus, the King decided to build a reception with a queue where each knight chooses in advance the time when he will come and how long the visit will take. The knights are served in the order of the recorded time, but each knight has to wait until the visits of all the knights before him are finished. Princess Keabeanie wants to see her father. However, she does not want to interrupt the knights so she joins the queue. Unfortunately, the knights change their minds very often — they can join the queue or cancel their visits. Please help the princess to understand how long she will have to wait until she sees her father if she enters the queue at the specified moments of time given the records at the reception.

输入输出格式

输入格式

The first line of the input contains a single integer $ q $ ( $ 1 \leq q \leq 3 \cdot 10^5 $ ) — the number of events. An event can be of three types: join, cancel, or query. - Join "+ $ t $ $ d $ " ( $ 1 \leq t, d \leq 10^6 $ ) — a new knight joins the queue, where $ t $ is the time when the knight will come and $ d $ is the duration of the visit. - Cancel "- $ i $ " ( $ 1 \leq i \leq q $ ) — the knight cancels the visit, where $ i $ is the number (counted starting from one) of the corresponding join event in the list of all events. - Query "? $ t $ " ( $ 1 \leq t \leq 10^6 $ ) — Keabeanie asks how long she will wait if she comes at the time $ t $ . It is guaranteed that after each event there are no two knights with the same entrance time in the queue. Cancel events refer to the previous joins that were not cancelled yet. Keabeanie can come at the same time as some knight, but Keabeanie is very polite and she will wait for the knight to pass.

输出格式

For each query write a separate line with the amount of time Keabeanie will have to wait.

输入输出样例

输入样例 #1

19
? 3
+ 2 2
? 3
? 4
+ 5 2
? 5
? 6
+ 1 2
? 2
? 3
? 4
? 5
? 6
? 7
? 9
- 8
? 2
? 3
? 6

输出样例 #1

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