Description

有一个序列 S ，初始为空。 请处理如下 Q个操作：

1 x：将 x 插入至 S 的末尾。

2 x c：从 S 中删除 c 个 x ，如果不够删就直接删完。

3：求 S 中最大值与最小值的差。

Format

Input

第一行给出Q

接下来Q行，代表Q个操作

Q<=2e5

x<=1e9

Output

如题

Samples

8
1 3
1 2
3
1 2
1 7
3
2 2 3
3

1
5
4