BST - Binary Search Tree

### 题目描述： 众所周知，二叉搜索树是一棵树，其中每个节点最多具有两个子节点（左子节点和右子节点）。 二叉搜索树的每个节点都有一个权值。对于每个节点如果存在一个权值$X$，则其左子树中的权值小于$X$，右子树中的权值大于$X$. 现在给你一个$1$~$N$（包括$N$）之间的整数序列，其中保证每个数字在序列中只出现一次。 请你将序列建成一颗二叉搜索树，我们规定将第一个数字的值存在根节点中，并按给定的序列顺序插入其他数字。 换句话说，你需要对每个插入的数字运行函数$insert(X$，$root)$： 该函数伪代码如下： 插入（编号X，节点N） 将计数器C增加1 if X小于节点N中的权值 if N没有左子节点 创建一个权值为X的新节点，并将其设置为节点N的左子节点 else insert（X，节点N的左子节点） else if （X大于节点N中的权值） if N没有右子节点 创建一个权值为X的新节点，并将其设置为节点N的右子节点 else insert（X，节点N的右子节点） 请你编写一个程序，计算在依次插入每个数字后计数器$C$的值并输出。计数器$C$最初为$0$。 输入输出格式 输入格式： 第一行包含一个正整数$N(1<=N<=300000)$ 之后有$N$行，每行一个数字，代表给定的序列。 输入数据保证这些数都是区间$[1,N]$中的整数且不会出现重复 输出格式： 一共$N$行，每行一个数字，表示按给定序列顺序插入每个数字之后计数器$C$的值 感谢@___new2zy___ 提供的翻译

A binary search tree is a tree in which every node has at most two children nodes (a left and a right child). Each node has an integer written inside it. If the number X is written inside a node, then the numbers in its left subtree are less than X and the numbers in its right subtree are greater than X. You will be given a sequence of integers between 1 and N (inclusive) such that each number appears in the sequence exactly once. You are to create a binary search tree from the sequence, putting the first number in the root node and inserting every other number in order. In other words, run insert (X, root) for every other number: ``` insert (number X, node N) increase the counter C by 1 if X is less than the number in node N if N has no left child create a new node with the number X and set it to be the left child of node N else insert (X, left child of node N) else (X is greater than the number in node N) if N has no right child create a new node with the number X and set it to be the right child of node N else insert (X, right child of node N) ``` Write a program that calculates the value of the counter C after every number is inserted. The counter is initially 0.

The first line contains the integer N (1 The remaining N lines contain the numbers in the sequence, integers in the interval \[1, N\]. The numbers will be distinct.

Output N integers, each on its own line, the values of the counter C after each number is inserted into the tree.

8
3
5
1
6
8
7
2
4

0
1
2
4
7
11
13
15