Problem7818--ABC253 —— C - Max - Min Query

7818: ABC253 —— C - Max - Min Query

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

SubmitSolved: 2Submit Num: 2StatisticsShowOff!

Description

We have a multiset of integers $S$, which is initially empty.
Given $Q$ queries, process them in order. Each query is of one of the following types.
  • 1 x: Insert an $x$ into $S$.
  • 2 x c: Remove an $x$ from $S\ m$ times, where $m=\text{min}(c,( \text{the number of} $x$\text{'s contained in} S))$.
  • 3 : Print ( minimum value of $S$). It is guaranteed that $S$ is not empty when this query is given.

Input

Input is given from Standard Input in the following format:
$Q$
query$_1$
$⋮$
query$_Q$
query$_i$, which denotes the $i$-th query, is in one of the following formats: 
1 x
2 x c
3

Output

Print the answers for the queries of type 3 in the given order, separated by newlines.

Constraints

$1≤Q≤2×10^5$
$0≤x≤10^9$
$1≤c≤Q$
When a query of type 3 is given, $S$ is not empty.
All values in input are integers.

Sample 1 Input 

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

Sample 1 Output 

1
5
4
The multiset $S$ transitions as follows.
  • 1-st query: insert 3 into S. S is now {3}.
  • 2-nd query: insert 2 into S. S is now {2,3}.
  • 3-rd query: the maximum value of S={2,3} is 3 and its minimum value is 2, so print 3−2=1.
  • 4-th query: insert 2 into S. S is now {2,2,3}.
  • 5-th query: insert 7 into S. S is now {2,2,3,7}.
  • 6-th query: the maximum value of S={2,2,3,7} is 7 and its minimum value is 2, so print 7−2=5.
  • 7-th query: since there are two 2's in S and min(2,3)=2, remove 2 from S twice. S is now {3,7}.
  • 8-th query: the maximum value of S={3,7} is 7 and its minimum value is 3, so print 7−3=4.

Sample 2 Input 

4
1 10000
1 1000
2 100 3
1 10

Sample 2 Output 

<nothing to print>
If the given queries do not contain that of type 3, nothing should be printed.

Source/Category

 
Submit