二叉搜索树的和值

题目

知识点：二叉搜索树，不是模拟

二叉搜索树是一种特殊的二叉树（每个节点最多只有两个儿子的树）。树的每个节点上存有一个唯一的值，并且满足：这个节点的左子树内所有点的值都比这个节点的值小，且右子树内所有点的值都比这个节点的值要大。

我们定义一棵二叉搜索树的和值为当前树的所有节点的深度和（根节点的深度为0）。现在有 N 个数需要插入一棵空树中。给定插入序列，请在每个元素被插入之后，输出当前树的和值。

输入

第一行为一个整数 n 接下来一行是n个各不相同的数字，这些数字在[1, n]区间。

($0<n<300000$)

输出

输出 n 行，第 i 行整数表示第 i个数插入树后，当前树的和值。

输入样例

8
3 5 1 6 8 7 2 4

输出样例

0
1
2
4
7
11
13
15