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 transformationsleft single rotations, right single rotations, left double rotations, and right double rotationsbut differ in exactly when and where these transformations are applied. Redblack trees are one of the most popular kinds of balanced binary search trees. In a redblack 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 redblack properties, based on the usual four rotations. In this problem, we will consider a simpler scheme for maintaining redblack trees, based on a single transformation, called a twist. Inserting a new key into a redblack 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 T4where T1, T2, T3, and T4 are subtrees (possibly empty). All four configurations are rewritten to exactly the same shape: (Red) y / \ / \ (Blk) x z (Blk) / \ / \ T1 T2 T3 T4After the twist, y's parent may be red, so the process continues until there are no more positions where a twist can be applied. Note that there will never be more than one red node with a red parent at the same time. 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 redblack 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)When we insert the 2 node, it goes on the right. The new node is colored red. 1 (Blk) \ 2 (Red)When we insert the 3 node, it again goes on the right and is colored red. 1 (Blk) \ 2 (Red) \ 3 (Red)The new node starts out red, but it has a red parent, so a twist is necessary. After the twist, the tree looks like 2 (Red) / \ (Blk) 1 3 (Blk)However, the root is recolored black at the end of every insert, so the final tree is 2 (Blk) / \ (Blk) 1 3 (Blk)Altogether, this series of inserts requires 1 twist, so your method should return 1.  
Definition  
 
Constraints  
  keys contains between 1 and 50 elements, inclusive.  
  keys is a permutation of the numbers between 1 and n, inclusive, where n is the length of keys.  
Examples  
0)  
 
1)  
 
2)  
 
3)  
 
4)  
