Implement a data structure that maintains a list of numbers and supports the following operations:

1. Insert a number in the end of the list
2. Insert a number in the beginning of the list
3. Sort the list in nondecreasing order
4. Output the number of inversions in the list

An inversion is a pair of indices (i, j) such that i < j and a_i > a_j where a_k is the kth element in the list.

Initially the list is empty.

Input

The first line of input contains one integer, q, the number of operations to perform. Each of next q lines describes an operation. The first integer of a line is the type of the operation. If the type of the operation is 1 or 2, the line contains also a number a_i, the number to be inserted in the list. If the type of the operation is 4, you should output the number of inversions in the list.

Output

For each operation of type 4, output the number of inversions in the list.

Constraints

• 1 \le q \le 5 \cdot 10^5
• 1 \le a_i \le 10^5

Examples

Input:

8
1 3
2 5
2 6
4
1 4
3
1 2
4

Output:

3
4