At Moloco, management and analysis of big data is an important part of its core business solution. One day, a very complicated issue was raised by a fellow employee, and you need to help resolve it.</p>

You are given an array A of n distinct integers that describe the raw data. You need to manipulate this array to obtain a new array S of n integers where S[i] = |{j : (1 ≤ j < i) ∧ (A[j] < A[i])}|. 

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

입력 형식

The first line contains an integer n between 1 and 1,000,000.</p>

The following n lines contain one integer per line where i+1th line describes A[i]. Assume |A[i]| ≤ 2,000,000,000.

출력 형식

Your output should consist of n lines where ith line contains a single integer that describes S[i].

예제 입력

5
10
5
12
1
11

예제 출력

0
0
2
0
3