Codeforces and Polygon may be unavailable from May 23, 4:00 (UTC) to May 23, 7:00 (UTC) due to technical maintenance. ×

I. McDaniel's
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

McDaniel's is a world–renowned restaurant run by Michelin Star Chef Ronald McDaniel.

Today is International Chef's Day, and Chef Ronald will be exclusively serving 1 item, the Ronald Burger. Chef Ronald intends to serve $$$N$$$ burgers with the $$$i^{th}$$$ burger having flavor value $$$f_i$$$.

You have recently been hired as a SWE intern at McDaniel's, and there is really no useful work for you to do, so Ronald gives you the following task:

For every burger $$$i$$$, count the number of burgers $$$j$$$ where:

1. $$$j < i$$$ and $$$f_j < f_i$$$

2. No burger $$$k$$$ exists where $$$j < k < i$$$ and $$$f_j < f_k$$$.

Input

The first line contains a single integer $$$N (1 \leq N \leq 10^5)$$$, the number of burgers Ronald will make.

The next line contains $$$N$$$ integers where the $$$i^{th}$$$ integer describes $$$f_i (1 \leq f_i \leq 10^9)$$$, the flavor value of the $$$i^{th}$$$ burger.

Output

Please output $$$N$$$ lines with the $$$i^{th}$$$ line containing a single integer: the count for the $$$i^{th}$$$ burger.

Examples
Input
5
1 3 5 2 4
Output
0
1
1
0
1
Input
10
1 2 3 4 5 6 7 8 9 10
Output
0
1
1
1
1
1
1
1
1
1
Input
8
7 9 1 5 2 3 6 4
Output
0
1
0
1
0
1
2
0
Input
8
7 6 5 4 3 2 1 8
Output
0
0
0
0
0
0
0
7
Input
2
1 1000000000
Output
0
1