// Arup Guha
// 2/4/2017
// Solution to AP Review Problem: Number of Inversions

import java.util.*;

public class inversions {
	
	public static void main(String[] args) {
		
		// Put random numbers into this list.
		ArrayList<Integer> list = new ArrayList<Integer>();
		
		Random r = new Random();
		
		// Put 10 random values into list.
		for (int i=0; i<10; i++) {
			
			// Get a new unique number.
			int num = r.nextInt(100);
			while (list.contains(num))
				num = r.nextInt(100);
				
			list.add(num);
		}
		
		// Print it.
		System.out.println(list);
		
		// Show result.
		System.out.println("Your list has "+numInversions(list)+" inversions.");
	}
	
	// Returns the number of inversions of list.
	public static int numInversions(ArrayList<Integer> list) {
		
		int res = 0;
		
		// Just try all pairs with i < j.
		for (int i=0; i<list.size(); i++)
			for (int j=i+1; j<list.size(); j++)
				
				// Here is when they are out of order, so add to our accumulator.
				if (list.get(i) > list.get(j))
					res++;
		
		// Ta da!
		return res;
	}
}