이진 검색 트리

P는 길이가 N인 배열이며, 0 이상 N - 1 이하의 정수가 중복 없이 한 번씩 들어 있다. 이 배열의 원소를 순서대로 삽입하여 이진 검색 트리를 만든다. 이진 검색 트리는 루트를 가진 이진 트리이고, 각 노드에는 하나의 정수 값이 저장된다.

먼저 루트 노드를 만들고 P[0]을 저장한다. 그 뒤 P[1]부터 P[N-1]까지 다음 순서로 삽입한다.

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

insert 함수는 다음과 같이 동작한다.

void insert(Vertex V, int X) {    if (X < V에 저장된 수) {        if (V에 왼쪽 자식이 있으면) {            insert(V의 왼쪽 자식, X);        } else {            V의 왼쪽 자식을 새로 만들고 X를 저장한다.        }    } else {        if (V에 오른쪽 자식이 있으면) {            insert(V의 오른쪽 자식, X);        } else {            V의 오른쪽 자식을 새로 만들고 X를 저장한다.        }    }}

노드의 높이는 루트에서 그 노드까지의 거리에서 1을 더한 값이다. N과 배열 P가 주어졌을 때, 위 방법으로 만든 이진 검색 트리의 모든 노드 높이의 합을 구하라.

첫째 줄에 자연수 N이 주어진다. N은 250,000 이하이다. 이어지는 N개의 줄에는 P[0]부터 P[N-1]까지의 원소가 한 줄에 하나씩 주어진다.

배열 P에는 0 이상 N - 1 이하의 정수가 중복 없이 모두 들어 있다.

주어진 배열 P로 이진 검색 트리를 만들었을 때, 모든 노드 높이의 합을 출력한다. 이 값은 2^63보다 작다.