二叉搜索树是一种树，其中每个节点最多有两个子节点（左子节点和右子节点）。每个节点内部都写有一个整数。如果节点内部写的数字是 $X$，那么其左子树中的数字都小于 $X$，其右子树中的数字都大于 $X$。

给你一个介于 $1$ 和 $N$（含）之间的整数序列，其中每个数字在序列中恰好出现一次。你需要根据该序列构建一棵二叉搜索树，将第一个数字作为根节点，并按顺序插入其他每个数字。换句话说，对其他每个数字运行 insert(X, root)：

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)

请编写一个程序，计算在插入每个数字后计数器 $C$ 的值。计数器初始为 $0$。

输入格式

第一行包含整数 $N$（$1 \le N \le 300000$），表示序列的长度。

接下来的 $N$ 行包含序列中的数字，为区间 $[1, N]$ 内的整数。这些数字互不相同。

输出格式

输出 $N$ 个整数，每行一个，表示每个数字插入树中后计数器 $C$ 的值。

子任务

在占总分 $50\%$ 的测试用例中，$N$ 最多为 $1000$。

样例

输入样例 1

4
1
2
3
4

输出样例 1

0
1
3
6

输入样例 2

5
3
2
4
1
5

输出样例 2

0
1
2
4
6

输入样例 3

8
3
5
1
6
8
7
2
4

输出样例 3

0
1
2
4
7
11
13
15