Array Manipulation at Moloco (Hard)

Interview

Time limit2sMemory limit512 MB

Summary

For each position i in a permutation-like array, count how many earlier elements are smaller than A[i], with n up to one million.

Level: Medium6 of 10
Topics: Segment tree, Binary search, Sorting, Array
Solved: No attempts yet

Problem

Managing and analyzing big data is an important part of Moloco's core business. One day a colleague brought in a tricky issue, and now you have to resolve it.

You are given an array $A$ of $n$ distinct integers that describes the raw data. From it you must build a new array $S$ of $n$ integers, where $S[i]$ is the number of elements that sit before position $i$ and are smaller than $A[i]$ .

$S[i] = |\{\, j : (1 \le j < i) \wedge (A[j] < A[i]) \,\}|$

For instance, if $A = [10, 5, 12, 1, 11]$ , then $S = [0, 0, 2, 0, 3]$ .

Input

The first line contains an integer $n$ . ( $1 \le n \le 1\,000\,000$ )

Each of the following $n$ lines contains one element of the array. Line $i+1$ holds $A[i]$ . All elements are distinct, and $|A[i]| \le 2\,000\,000\,000$ .

Output

Print $n$ lines. Line $i$ contains the single integer $S[i]$ .

Examples6

Example 1
Input
```
5
10
5
12
1
11
```
Expected output
```
0
0
2
0
3
```
Example 2
Input
```
1
-2000000000
```
Expected output
```
0
```
Example 3
Input
```
8
3
1
4
-1
5
-9
2
6
```
Expected output
```
0
0
2
0
4
0
3
7
```
Example 4
Input
```
7
1
2
3
4
5
6
7
```
Expected output
```
0
1
2
3
4
5
6
```
Example 5
Input
```
7
7
6
5
4
3
2
1
```
Expected output
```
0
0
0
0
0
0
0
```
Example 6
Input
```
2
5
-5
```
Expected output
```
0
0
```