이진 검색 트리 깊이 합
문제
길이 N인 배열의 원소를 순서대로 이진 검색 트리에 삽입한다.
각 원소가 삽입되는 노드의 깊이를 루트 깊이 1로 계산할 때, 모든 삽입 원소의 깊이 합을 출력하라.
입력
첫째 줄에 N이 주어진다.
N은 250,000보다 작거나 같은 자연수이다.
둘째 줄부터 N개의 줄에 P[0]부터 P[N-1]의 원소가 한 줄에 하나씩 들어온다.
출력
주어진 P 배열로 이진 검색 트리를 만들었을 때, 삽입된 모든 노드의 깊이 합을 출력한다.
이 값은 2^63보다 작다.
예제 입력 1
10
9
1
4
3
2
5
6
7
8
0예제 출력 1
40예제 입력 2
10
6
3
2
7
9
4
8
1
0
5예제 출력 2
31예제 입력 3
10
0
1
2
3
4
5
6
7
8
9예제 출력 3
55