#1113 Inversion

124  10 s   128 MB  

Description

N개의 정수로 이뤄진 수열 A = { a1, a2, …, aN, }이 주어졌을 때, 1≤i<j≤N 이고 ai>aj을 만족하는 쌍 (i,j)의 개수를 세는 프로그램을 작성하라.

 

Input

입력은 표준 입력(Standard input)으로 이뤄진다.

입력의 첫째 줄에는 N(1≤N≤105)이 입력된다. 둘째 줄에는 a1, a2, …, aN(0≤ai≤109)이 입력된다. ai ai+1 사이에는 공백(white-space)가 한 칸 들어간다. 주어진 형식을 벗어나는 입력은 들어오지 않는다.

 

Output

출력은 표준 출력(Standard output)으로 이뤄진다.

입력 된 수열에 대해 위의 조건을 만족하는 쌍의 개수를 출력한다.

 

Sample Input

Sample Output

5
2 3 1 5 4
3

HINT

Brute force 기법을 이용할 경우 시간 복잡도가 O(N2) 이므로 제시간 안에 답이 나오지 않는다. Merge sort나 Balanced binary search tree를 이용할 경우 제시간에 답을 구할 수 있다.

C/C++을 사용할 경우 답이 32-bit signed integer 범위를 넘어갈 가능성이 있으며,  64 bit-integer 형식인 'long long'을 사용하면 해결 할 수 있으며 사용법은 다음과 같다.

long long value;
value = 0LL; // 0만을 써도 올바른 값이 들어가나, 뒤에 LL을 붙이는 것을 권장한다. 입/출력을 제외하면 사용법은 int와 동일하다.
scanf("%lld", &value); // 입력은%lld format을 사용한다.
printf("%lld", value); // 출력은 %lld로 format을 사용한다.