정수로 이루어진 수열 \(A=(A_1,A_2,\dots,A_N)\)이 주어진다.

두 인덱스 \(i\), \(j\)가 다음 조건을 모두 만족하면 \((i,j)\)를 수열 \(A\)의 역전쌍이라고 한다.

• \(1 \le i < j \le N\)
• \(A_i>A_j\)

수열 \(A\)에 존재하는 역전쌍의 개수를 구하여라. 두 원소의 값이 같으면 역전쌍으로 세지 않는다.

입력

첫째 줄에 수열의 크기 \(N\)이 주어진다.

둘째 줄에 \(N\)개의 정수 \(A_1,A_2,\dots,A_N\)이 공백으로 구분되어 주어진다.

출력

수열 \(A\)에 존재하는 역전쌍의 개수를 출력한다.

답은 32비트 정수 범위를 벗어날 수 있다.

제한 사항

• \(1 \le N \le 500,000\)
• \(-1,000,000,000 \le A_i \le 1,000,000,000\)

예제 입력 1

5
5 3 2 4 1

예제 출력 1

8

예제 설명 1

역전쌍은 \((1,2)\), \((1,3)\), \((1,4)\), \((1,5)\), \((2,3)\), \((2,5)\), \((3,5)\), \((4,5)\)로 총 \(8\)개이다.