Red-Black Tree Insertions and Rotations

Koridoly is maintaining an initially empty red–black tree and will perform \(n\) operations. The tree follows the standard red–black tree insertion algorithm, with a twist: for duplicate integers, the later insertion is considered to be smaller than the earlier one.

There are two kinds of operations:

• \(op = 1\): Insert an integer \(x\) into the red–black tree.
• \(op = 2\): Given an integer \(x\), consider all integers in the range \([1,x]\) that have been inserted into the red–black tree. If one of these is chosen uniformly at random (each inserted number in \([1,x]\) has the same probability of being chosen), let \(r\) be the number of rotations performed during its insertion. Output \(x \times E[r]\), i.e. the expected number of rotations multiplied by \(x\). (It can be proved that \(x\times E[r]\) is an integer.)

Note: The red–black tree insertion is implemented exactly according to the standard algorithm. In particular, during the insertion fix-up, whenever a left or right rotation happens, it is counted towards the rotation count of the inserting number.

Red–black tree insertion reminder:

// Pseudocode snippet:
function RB-INSERT(T, z):
    z.color = RED
    Insert z into tree T using the BST insertion rule. For comparison:
         if z.key  y.timestamp, go left.
    z.left = T.NIL
    z.right = T.NIL

    // Fixup
    currentRotationCount = 0
    while (z.parent.color == RED):
         if (z.parent == z.parent.parent.left):
              y = z.parent.parent.right
              if (y.color == RED):
                   z.parent.color = BLACK
                   y.color = BLACK
                   z.parent.parent.color = RED
                   z = z.parent.parent
              else:
                   if (z == z.parent.right):
                        z = z.parent
                        LEFT-ROTATE(T, z)   // currentRotationCount++
                   z.parent.color = BLACK
                   z.parent.parent.color = RED
                   RIGHT-ROTATE(T, z.parent.parent)  // currentRotationCount++
         else:  // symmetric
              ...
    T.root.color = BLACK
    // Record the number of rotations performed for this insertion as currentRotationCount

inputFormat

The first line contains an integer \(n\) indicating the number of operations.

Each of the next \(n\) lines contains two integers \(op\) and \(x\). If \(op = 1\), insert \(x\) into the red–black tree. If \(op = 2\), query the expected rotation count as described.

outputFormat

For each query operation \(op = 2\), output a single line containing one integer: \(x \times E[r]\), which is guaranteed to be an integer.

sample

2
1 10
2 10

0