Algorithms and Data Structures

Number of swaps performed by Heapify

Given an initially empty heap, you are asked to perform q queries. There are 2 types of queries:
  1. add x - should add x to the heap
  1. pop - should delete the root of the heap
For each of the queries, you are asked to print the number of swaps needed to restructure the heap to make it satisfy the max-heap property.
For the pop operations, the swapping of the root and the last element is also counted as a swap.

Input

The first line of the input contains a single integer q (1 ≤ q ≤ ).
The next q lines contain queries - each on a separate line. It’s guaranteed that for all add queries the value of x does not exceed in absolute value.

Output

The program should print the number of swap operations each on a separate line.

Examples

Input
Output
7 add 1 add 2 add -3 add 4 pop add -2 pop
0 1 0 2 2 0 2
 

Constraints

Time limit: 1 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue