Binary Search Tree

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.

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.

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.