#백준_1517 버블 소트

# 유형 : 분할 정복, 정렬

# 제목은 버블 소트이지만, 버블 소트를 쓰면 바로 시간초과 남, 병합 정렬을 할 때 cnt를 세는 부분만 추가하면 된다. 카운트 증가는 병합 과정에서 왼쪽 값이 오른쪽 값 보다 클 때 왼쪽 배열에 있는 원소의 갯수만큼 계속 더해주면 된다.

package bj;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class p1517 {
	static long cnt=0;
	static long tmp[];
	static long arr[];
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		arr = new long[N];
		tmp = new long[N];
		for(int i=0; i<N; i++)
			arr[i] = Long.parseLong(st.nextToken());
		
		mergeSort(0, arr.length-1);
		System.out.println(cnt);
	}
	
	public static void mergeSort(int begin, int end) {
		if(begin<end) {
			int middle = (begin+end)/2;
			mergeSort(begin, middle);
			mergeSort(middle+1, end);
			merge(begin,middle,end);
		}
	}

	private static void merge(int begin, int middle, int end) {
		// TODO Auto-generated method stub
		int i = begin;
		int j = middle+1;
		int t = begin;
		
		while(i<=middle && j<=end) {
			if(arr[i] <= arr[j]) {
				tmp[t++] = arr[i++];
			}else {
				tmp[t++] = arr[j++];
				cnt +=  (middle + 1 - i);
			}
		}
		while(i<=middle)
			tmp[t++] = arr[i++];
		while(j<=end)
			tmp[t++] = arr[j++];
		
		for(int k=begin; k<=end; k++) {
			arr[k] = tmp[k];
		}
		
	}
}