BOJ. Bubble Sort (1517)

import java.util.*;
import java.io.*;

public class Main {
	static BufferedReader br;
	static int max = 0, maxIdx = 0;
	public static void main(String[] args) throws IOException {
		br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		String[] line;
		int n = toi(br.readLine());
		int[] arr = new int[n];
		int[] seg = new int[1 << (int)Math.ceil(Math.log(n) / Math.log(2)) + 1];
		ArrayList<int[]> al = new ArrayList<>();

		line = getLine();
		for(int i = 0; i < n; i++) al.add(new int[] { toi(line[i]), i });

		al.sort((l, r) -> {
			if(l[0] == r[0]) return r[1] - l[1];
			return r[0] - l[0];
		});
		long sum = 0;


		for(int i = 0; i < n; i++) {
			int[] pair = al.get(i);
			sum += get(seg, 0, n - 1, 0, pair[1], 1);
			update(seg, 0, n - 1, pair[1], 1);
		}
		print(sum);
	}

	static int get(int[] seg, int left, int right, int start, int end, int idx) {
		if(right < start || end < left) return 0;
		if(start <= left && right <= end) return seg[idx];
		int mid = (left + right) / 2;
		return get(seg, left, mid, start, end, 2 * idx) + get(seg, mid + 1, right, start, end, 2 * idx + 1);
	}

	static void update(int[] seg,  int left, int right, int targetIdx, int idx) {
		seg[idx]++;
		if(left == right) return;
		int mid = (left + right) / 2;
		if(left <= targetIdx && targetIdx <= mid) update(seg, left, mid, targetIdx, 2 * idx);
		else update(seg, mid + 1, right, targetIdx, 2 * idx + 1);
	}

	static int toi(String s) { return Integer.parseInt(s); }
	static String[] getLine() throws IOException { return br.readLine().split(" "); }
	static <T> void print(T s) { System.out.print(s); }
	static <T> void println(T s) { System.out.println(s); }
}