Reference no: EM131116560

Heap
This question is designed to help you get a better understanding of basic heap operations. You will be given queries of 3 types:
• "1 v" -Add an element v to the heap.
• "2 v" -Delete the element v from the heap.
• "3" -Print the minimum of all the elements of the heap.
NOTE: It is guaranteed that the element to be deleted will be there in the heap. Also, at any instant, only distinct elements will be in the heap.

Input Format
The first line contains the number of queries, Q.
Each of the next Q lines contains a single query of any one of the 3 above mentioned types.

Constraints
1 ≤ Q ≤ 10^5
-10^9 ≤ v ≤ 10^9

Output Format
For each query of type 3, print the minimum value on a single line.

Sample Input
5
1 4
1 9
3
2 4
3

Sample Output
4
9

Explanation
After the first 2 queries, the heap contains {4,9}. Printing the minimum gives 4 as the output.Then, the 4th query deletes 4 from the heap, and the 5th query gives 9 as the output.

Minimum Average Waiting Time
Tieu owns a pizza restaurant and he manages it in his own way. While in a normal restaurant, a customer is served by following the first-come, first-served rule, Tieu simply minimizes the average waiting time of his customers. So he gets to decide who is served first, regardless of how sooner or later a person comes.
Different kinds of pizzas take different amounts of time to cook. Also, once he starts cooking a pizza, he cannot cook another pizza until the first pizza is completely cooked. Let's say we have three customers who come at time t=0, t=1, & t=2 respectively, and the time needed to cook their pizzas is 3, 9, & 6 respectively. If Tieu applies first-come, first-served rule, then the waiting time of three customers is 3, 11, & 16 respectively. The average waiting time in this case is (3 + 11 + 16) / 3 = 10. This is not an optimized solution. After serving the first customer at time t=3, Tieu can choose to serve the third customer. In that case, the waiting time will be 3, 7, & 17
respectively. Hence the average waiting time is (3 + 7 + 17) / 3 = 9. Help Tieu achieve the minimum average waiting time. For the sake of simplicity, just find the integer part of the minimum average waiting time.

Input Format
• The first line contains an integer N, which is the number of customers.
• In the next N line, the ith line contains two space separated numbers Ti and Li. Ti is the time when the ith customer order a pizza, and Li is the time required to cook that pizza.

Output Format
• Display the integer part of the minimum average waiting time.

Constraints
1 ≤ N ≤ 10^5
0 ≤ Ti ≤ 10^9
1 ≤ Li ≤ 10^9

Note
• The waiting time is calculated as the difference between the time a customer orders pizza (the time at which they enter the shop) and the time she is served.
• Cook does not know about the future orders.

Sample Input #00
3
0 3
1 9
2 6

Sample Output #00
9

Sample Input #01
3
0 3
1 9
2 5

Sample Output #01
8

Explanation #01
Let's call the person ordering at time = 0 as A, time = 1 as B and time = 2 as C. By delivering pizza for A, C and B we get the minimum average wait time to be
(3 + 6 + 16)/3 = 25/3 = 8.33
the integer part is 8 and hence the answer.