Cost Analysis of Spaly Operations

In the country of H, the splay tree is a fundamental data structure taught from an early age. However, a misguided belief in a variant called "spaly" (using single rotations only) has taken hold among some people. To counter this, the king of H has constructed a sequence of m operations, and your task is to compute the actual cost of each operation according to the spaly rules described below.

Spaly Overview:

• A spaly is a binary search tree. For any node x, if l_x is its left child then l_x's key is less than x's key, and if r_x is its right child then r_x's key is greater than x's key.
• The depth of a node is defined as the number of nodes on the unique path from the root to that node (including the node itself). Formally, the depth of a node x is defined as \[ \text{depth}(x)=\#\{\text{nodes on the path from the root to } x\}, \] using LaTeX format for the formula.
• A single rotation (zig or zag) is performed on a node x with parent f. If x is the left child of f, perform a zig (right rotation); otherwise, perform a zag (left rotation). Each such rotation decreases the depth of x by 1. Repeating these rotations until x becomes the root is called single rotation splaying.

Operations (each operation yields a cost):

1. Insert (op = 1): Insert a new node with key key into the current (non-empty) spaly tree. The insertion procedure is as follows: Starting from the root, repeatedly compare key with the current node’s key. Go to the left child if key is smaller or to the right child if larger. When you reach a node x where if key is smaller and x has no left child, or if key is larger and x has no right child, insert the new node as that child. The cost of the insertion is the depth of the newly inserted node. If the tree is empty, simply create a new single-node tree (with cost 1).
2. Single Rotation Minimum (op = 2): Let x_min be the node with the smallest key. Record its depth as the cost, then perform single rotation splaying on x_min so that it becomes the root.
3. Single Rotation Maximum (op = 3): Let x_max be the node with the largest key. Record its depth as the cost, then splay x_max to the root.
4. Single Rotation Delete Minimum (op = 4): First perform the single rotation minimum operation (i.e. op = 2) to bring the smallest element to the root, then delete the root. (As guaranteed, after the rotation the root will have no left child, so simply remove the link to the right subtree.) The cost is the cost of the splay operation (the depth of the node before rotation).
5. Single Rotation Delete Maximum (op = 5): First perform the single rotation maximum operation (i.e. op = 3) to bring the largest element to the root, then delete the root. The cost is the cost of the splay operation (the depth of the node before rotation).

You are guaranteed that all operations are valid (e.g. deletion operations will only be performed when the tree is non-empty). Process the m operations in order and output the cost incurred for each operation.

inputFormat

The first line contains an integer m (the number of operations, \(1 \le m \le 10^5\)). Each of the next m lines describes an operation in one of the following formats:

• For an insert operation: 1 key (where key is an integer and all keys are distinct).
• For the other operations: a single integer 2, 3, 4, or 5 corresponding to the operation types described above.

outputFormat

Output m lines. The i-th line should contain a single integer representing the cost of the i-th operation.

sample

7
1 10
1 5
1 15
2
3
4
5

1
2
2
2
3
3
1