题目背景

翻译自 NERC 2018 K 题。

题目描述

有些骑士想要拜访国王，但是由于这里的骑士都很遵守礼节，他们都会提前预约好他要来拜访的时刻和拜访将持续的时间。骑士按照接待处记录的时刻顺序依次拜访国王，每个骑士必须等前面的骑士结束拜访。

很不幸，公主也准备要来拜访国王，但善良的公主并不会为此而打乱骑士们拜访的顺序，而她会等待骑士们拜访完了再来拜访，请你计算公主要等多长时间。

输入格式

共 $q+1$ 行。

第一行一个整数 $q (1 \leq q \leq 3 \times 10^5)$。

然后 $q$ 行，先是一个字符。

• 如果字符是 +，紧跟在后面两个数字，表示骑士 $i$ 要于 $t (1 \leq t \leq 10^6)$ 时刻到达，拜访时间 $d(1 \leq d \leq 10^6)$ 时间单位。

• 如果字符是 -，后面一个数字 $i(1 \leq i \leq q)$，表示骑士 $i$ 暂时取消了他的预约。

• 如果字符是 ?，后面一个数字 $t (1 \leq t \leq 10^6)$，表示公主将于 $t$ 时刻拜访。

输出格式

对于每个 ?，输出一行，表示公主要等待多长时间。注意此处公主拜访时骑士的预约记录只有前面的几个，并不包含后面加进来的。

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

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

提示

对于所有数据，保证 $1 \leq q \leq 3 \times 10^5$，$1 \leq t \leq 10^6$，$1 \leq d \leq 10^6$。