15517번 - Array Manipulation at Moloco (Hard) 다국어

문제

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.

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.

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].

제한

힌트