McDaniel's
Description
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$.
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.
Please output $N$ lines with the $i^{th}$ line containing a single integer: the count for the $i^{th}$ burger.
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.
5
1 3 5 2 4
10
1 2 3 4 5 6 7 8 9 10
8
7 9 1 5 2 3 6 4
8
7 6 5 4 3 2 1 8
2
1 1000000000
0
1
1
0
1
0
1
1
1
1
1
1
1
1
1
0
1
0
1
0
1
2
0
0
0
0
0
0
0
0
7
0
1