Binary Search Tree

Time limit2sMemory limit256 MB

Summary

Given the insertion order of 0..N-1 values, compute the sum of node heights in the resulting binary search tree efficiently for N up to 250000.

Level: Medium7 of 10
Topics: Tree, Divide and conquer, Segment tree, Recursion
Solved: No attempts yet

Problem

P is an array of length N containing each integer from 0 to N - 1 exactly once. A binary search tree is built by inserting the values of P in order. The tree is rooted, and each node stores one integer.

First, create the root and store P[0] in it. Then insert P[1] through P[N-1] as follows.

for (int i = 1; i <= N - 1; i++) {
    insert(root, P[i]);
}

The insert function behaves as follows.

void insert(Vertex V, int X) {
    if (X < the value stored in V) {
        if (V has a left child) {
            insert(V's left child, X);
        } else {
            create V's left child and store X there;
        }
    } else {
        if (V has a right child) {
            insert(V's right child, X);
        } else {
            create V's right child and store X there;
        }
    }
}

The height of a node is its distance from the root plus 1. Given N and P, compute the sum of the heights of all nodes in the resulting binary search tree.

Input

The first line contains a positive integer N. N is at most 250,000. The next N lines contain the elements from P[0] through P[N-1], one per line.

The array P contains every integer from 0 to N - 1 exactly once.

Output

Print the sum of the heights of all nodes after building the binary search tree from the given array P. This value is less than 2^63.

Examples3

Example 1
Input
```
10
9
1
4
3
2
5
6
7
8
0
```
Expected output
```
40
```
Example 2
Input
```
10
6
3
2
7
9
4
8
1
0
5
```
Expected output
```
31
```
Example 3
Input
```
10
0
1
2
3
4
5
6
7
8
9
```
Expected output
```
55
```