Zadání úlohy z A4B33ALG

Lazy AVL Tree

Distinguished professor Fabinaris Suchbaum and his team in Max Planck Institute for Software Systems in Saarbrücken are famous for their long-term research in binary search trees. Recently, they proposed a special variant of the AVL tree, called Lazy AVL tree. It implements insert operation in the same way as the standard AVL tree, but delete operation only marks nodes as deleted, without changing the tree structure. To maintain good properties of the tree, marked nodes are physically deleted during a so called consolidation phase. This phase is launched whenever the tree has a path from its root to a leaf that contains many nodes marked as deleted.

Notation
For a Lazy AVL tree T, let height(T) denote its height. It is defined as the number of edges of the longest path from the root to a leaf. In addition, it equals −1 if T is empty. For a node X of T, let Key(X) denote its key. Assume that each node has a boolean flag determining whether the node stores a deleted key or not. We use deleted(X) to denote the value of the flag for X. We say that a node X is marked as deleted if and only if deleted(X)=true.

Insert(k)
If key k is in T in a node X, then the operation sets deleted(X):=false. If key k is not in T, it is inserted by applying the standard AVL tree rules.

Delete(k)
If key k is in T in a node X, then the operation sets deleted(X):=true. If key k is not in T, the operation does not perform any change.

Consolidation
The consolidation is automatically activated after performing any insert or delete operation that causes that upon its finishing T has a path from the root to a leaf containing at least 1+⌊height(T)/2⌋ nodes marked as deleted. If this situation occurs, then, until there is a node marked as deleted, the consolidation takes the node X marked as deleted which is first in the postorder ordering and calls remove(X), where the remove operation is defined bellow.

Remove(X)
To physically remove node X from a Lazy AVL T, apply the following recursive rules:

If X is a leaf, perform standard AVL delete of X to remove it from T and to rebalance T if needed. When the standard AVL delete can rebalance a node by a single as well as double rotation, the single rotation is always preferred.
If X has a left child, in the left subtree of X, find the node Y with the maximum key. Set Key(X):=Key(Y), deleted(X):=false. Call remove(Y).
If X has not a left child but it has a right child, in the right subtree of X, find the node Y with the minimum key. Set Key(X):=Key(Y), deleted(X):=false. Call remove(Y).

To illustrate the operations, let us consider the following example of a Lazy AVL tree:

   2+
1+    3+
         4+

It contains four keys and its height is 2. The symbol "+" appended to each key indicates that none of the nodes is marked as deleted. If we perform delete(3), the tree structure does not change. We obtain

   2+
1+    3-
         4+

where the symbol "−" appended to key 3 indicates that the node storing this key has been marked as deleted. Operation insert(5) inserts a new node and applies a single rotation needed to rebalance the node with key 3.

   2+
1+       4+
      3-    5+

Operation insert(3) finds the node with key 3 and sets its deleted flag to false.

   2+
1+       4+
      3+    5+

Calling delete(5) and delete(2) produces the tree

   2-
1+       4+
      3+    5-

which activates the consolidation phase (since there is a path from the root to a leaf with 2 ≥ 1+⌊2/2⌋ nodes marked as deleted). The consolidation procedure first removes the node with key 5, obtaining the tree

   2-
1+       4+
      3+

and then it removes the root. To do it, the key in the root is replaced by key 1 form the left subtree and the leaf containg key 1 is removed.

1+
       4+
    3+

Now, a double rotation is applied in the root to obtain the resulting balanced tree

   3+
1+    4+

The task

Implement the Lazy AVL tree. Starting with an empty Lazy AVL tree T, perform a sequence of insert and delete operations over T. Count the total number of rotations and consolidations performed during this process.

Input

The first input line contains an integer N which is the number of operations to be performed. Each of the next N lines contains one nonzero integer. If it is a positive integer K, then the line represents operation insert(K). Otherwise the line represents operation delete(|K|). The operations are performed in the same order as they appear in the input.
It holds 1 ≤ N ≤ 2×10⁶ and |K| ≤ 1.5×10⁶.

Output

The output consists of one line containing integers H, R, and C separated by spaces. H is the height of the tree after performing all the operations. R is the total number of rotations performed during all the operations (including those performed during consolidation phases). Any single rotation counts as 1. Any double rotation counts as 2. C is the total number of performed consolidations.

Examples

Input

Output

1 3 1

Input

Output

1 3 2

Input

Output

-1 2 4

Public data

The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.
Link to public data set