P6412 [COCI 2008/2009 #3] BST

现在有一个 $1\sim n$ 的排列 $a$，将序列中的元素依次放进一个 BST 里，求 BST 中插入函数的执行次数。 **注意：第一个数已经作为 BST 的根。** 如果您无法理解上面说的话，这里有一份伪代码： ``` insert( number x, node n ) c+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) ``` 您需要求的就是上面的 insert 函数每进行一次后 $c$ 的值。 **再次注意：第一个数已经作为 BST 的根。**

无

无

#### 数据范围及限制 - 对于 $50\%$ 的数据，保证 $n\le 10^3$。 - 对于 $100\%$ 的数据，保证 $1\le n\le 3\times 10^5$，$1\le a_i\le n$，$a_i$ 互不相同。 #### 说明 本题译自 [Croatian Open Competition in Informatics 2008/2009](https://hsin.hr/coci/archive/2008_2009) [Contest #3](https://hsin.hr/coci/archive/2008_2009/contest3_tasks.pdf) T5 BST。