Problem Statement

Balanced binary search trees are among the most studied data structures in computer science. However, implementing them can be rather tricky. Most designs of balanced binary search trees are based on the same four basic transformations--left single rotations, right single rotations, left double rotations, and right double rotations--but differ in exactly when and where these transformations are applied.

Red-black trees are one of the most popular kinds of balanced binary search trees. In a red-black tree, every node is colored either red or black, and no red node is allowed to have a red parent. In addition, every path from the root to a leaf contains the same number of black nodes. Most books on data structures contain a description of how to maintain the red-black properties, based on the usual four rotations. In this problem, we will consider a simpler scheme for maintaining red-black trees, based on a single transformation, called a twist.

Inserting a new key into a red-black tree proceeds in two phases: a search phase followed by a rebalancing phase. In the search phase, you start at the root and walk down the tree, going left when the new key is smaller than the key at the current node and going right when the new key is larger than the key at the current node. (You may assume the new key will not be equal to the key at the current node.) When the search reaches the bottom of the tree, the new key is added as a new child of the last node in the search path, on the left or right, as appropriate. The new node is always a leaf and is always colored red.

If the new node's parent is also red, then we now have a violation of the rule that no red node may have a red parent. The job of the rebalancing phase is to detect such situations, and to correct them using a transformation called a twist. A twist involves the red node, its red parent, and its black grandparent. There are four possible configurations for these three nodes, shown below:

     (Blk) z         (Blk) z               x (Blk)         x (Blk)
          / \             / \             / \             / \
   (Red) y   T4    (Red) x   T4         T1   z (Red)    T1   y (Red)
        / \             / \                 / \             / \
 (Red) x   T3         T1   y (Red)   (Red) y   T4         T2   z (Red)
      / \                 / \             / \                 / \
    T1   T2             T2   T3         T2   T3             T3   T4

                             (Red) y
                                  / \
                                 /   \
                          (Blk) x     z (Blk)
                               / \   / \
                              T1 T2 T3 T4  

There is one last case to worry about. It is possible to have a red node with a red parent, but with no grandparent because the parent is the root. A twist cannot be applied without the grandparent, so to protect against this case, we color the root black at the end of every insert.

Given a sequence of numbers to be inserted one at a time into an initially empty red-black tree, your task is to determine the total number of twists that occur during the inserts.

As an example, consider the steps involved in inserting the numbers {1,2,3}. Initially the tree is empty, so when we insert the 1 node, it becomes the new root. The new node starts out red, but, because it is the root, it is recolored black at the end of the insert. The tree now looks like

            1 (Blk)

            1 (Blk)
             \
              2 (Red)

            1 (Blk)
             \
              2 (Red)
               \
                3 (Red)

            2 (Red)
           / \
    (Blk) 1   3 (Blk)

            2 (Blk)
           / \
    (Blk) 1   3 (Blk)

Definition

Constraints

Examples