题目：二叉查找树

题目描述

相信大家对二叉查找树都很熟悉了，现在给你N 个整数的序列，每个整数都在区间[1,N]内，且不重复。现在要你按照给定序列的顺序，建立一个二叉查找树，把第一个整数作为根，然后依次插入后面的整数。

你的任务是：

每次把序列的一个整数插入到二叉查找数后，到目前为止计数累加器C的值是多少？请把它输出。注意：第一次插入根，计数器C的值是0，你可以理解为插入根是不执行insert()操作的，其后每插入一个结点，C都累加，也就是每次进入过程insert( numberX, node N )，都会执行increase the counter C by 1，使得C不断增大。

输入输出格式

输入格式：

第一行一个整数：N, 表示序列有多少个整数。1 <= N <=300000 接下来有N 行，每行一个整数X, X 在区间[1,N]内，且不重复，这N 个整数就组成了一个有序的序列。

输出格式：

N 行，每行一个整数，第一行表示你把序列的第一个数插入到二叉查找树后，当前计数器C的值是多少。50%的数据：N <= 1000

输入样例1 4 1 2 3 4

输出样例1 0 1 3 6