Binary Search Tree

Source: Kattis

Version: Phuoc Hung OJ Extended

Problem Statement

A permutation of the integers from $1$ to $n$ is given. Build a binary search tree in exactly this order: the first number becomes the root; for every later number, start at the root, go left when the new number is smaller and right when it is larger, until an empty child position is reached and the new node is created there.

The root has depth $0$. The depth of any other node is the number of edges from the root to that node.

A counter $C$ is initially $0$. After each insertion, add the depth of the newly inserted node to $C$, then print the current value of $C$.

The first inserted value is the root, so its depth is $0$ and the first printed counter value is also $0$.

Input

The first line contains $n$.

The next $n$ lines contain $a_1,a_2,\ldots,a_n$ in order. The sequence is a permutation of $1,2,\ldots,n$.

Output

Print exactly $n$ lines. Line $i$ is the value of $C$ immediately after inserting $a_i$.

Subtasks

Subtask 1 (20 points): $1\le n\le 20$.

Subtask 2 (30 points): $1\le n\le 5000$.

Subtask 3 (50 points): $1\le n\le 300000$.

In all subtasks, $a_1,a_2,\ldots,a_n$ is a permutation of the integers from $1$ through $n$.

Examples

Input

8
3
5
1
6
8
7
2
4

Output

0
1
2
4
7
11
13
15

Explanation

The depths of the newly inserted nodes are $0,1,1,2,3,4,2,2$.

Starting from $C=0$ and adding these depths after each insertion gives $0,1,2,4,7,11,13,15$, matching the eight output lines.