용사 길드의 훈련 기록부에는 \(N\)명의 용사가 각자 고유한 실력 점수를 가지고 순서대로 줄을 서 있다. 점수가 높은 용사가 낮은 용사보다 앞에 서 있으면 그 두 명을 역전쌍이라 한다. 즉, 인덱스 \(i < j\)인 두 용사의 점수를 \(a_i\), \(a_j\)라 할 때 \(a_i > a_j\)이면 역전쌍이다.

훈련 대장은 이 기록부에서 역전쌍이 몇 쌍인지 알고 싶다. 역전쌍의 수를 구하여라.

• \(1 \le N \le 200\,000\)
• 각 용사의 점수는 \(1\) 이상 \(10^9\) 이하의 정수이다.

첫째 줄에 용사의 수 \(N\)이 주어진다.

둘째 줄에 \(N\)명의 실력 점수가 줄 서 있는 순서대로 공백으로 구분되어 주어진다. 같은 점수를 가진 용사가 여러 명 있을 수 있으며, 점수가 같은 두 용사는 역전쌍으로 세지 않는다.

역전쌍의 수를 출력한다.

riseoj 작성

출처 Original