Moloco 배열 변환 (어려움)

대용량 데이터의 관리와 분석은 Moloco의 핵심 사업에서 중요한 부분이다. 어느 날 동료가 까다로운 문제를 들고 왔고, 이제 당신이 해결해야 한다.

원본 데이터를 나타내는, 서로 다른 정수 $n$개짜리 배열 $A$가 주어진다. 이 배열로 길이가 $n$인 새 배열 $S$를 만들어야 한다. $S[i]$는 자기 앞에 놓이면서 값이 $A[i]$보다 작은 원소의 개수다.

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

예를 들어 $A = [10, 5, 12, 1, 11]$이면 $S = [0, 0, 2, 0, 3]$이다.

첫째 줄에 정수 $n$이 주어진다. ($1 \le n \le 1\,000\,000$)

이어지는 $n$개 줄에 배열의 원소가 한 줄에 하나씩 주어진다. $i+1$번째 줄의 수가 $A[i]$다. 모든 원소는 서로 다르고, $|A[i]| \le 2\,000\,000\,000$이다.

$n$개의 줄을 출력한다. $i$번째 줄에는 $S[i]$를 정수 하나로 출력한다.