// you can also use imports, for example:
// import java.util.*;

// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    int [] global_A;
    public int solution(int[] A) {
        // write your code in Java SE 8
        global_A = A.clone();
        return mergesort(global_A, 0, global_A.length-1);
    }
    
    public int mergesort(int[]A, int first, int last){
		int mid = (first+last)/2;
		int left_inver, right_inver;
		if(first < last){
			//Recursive calling
			left_inver = mergesort(A, first, mid);
			if(left_inver == -1)
				return -1;
			
			right_inver = mergesort(A, mid+1, last);
			if(right_inver == -1)
				return -1;
		}
		else{ // Terminate condition
			return 0;
		}
		
		int first_index = first; // 왼쪽 부분값의 인덱스
		int second_index = mid+1; // 오른쪽 부분의 인덱스
		
		int[] temp = new int[last-first+1];
		int temp_index = 0;
		int merge_inver = 0; // inversion한 횟수
		
		//왼쪽 인덱스의 위치가 mid보다 작고 오른쪽 인덱스 위치가 last보다 작을때까지 반복
		while(first_index <= mid && second_index <= last){
			
			// P < Q 에 해당하지 않기 때문에 inversion이 이루어 지지 않는 조합
			if(A[first_index] <= A[second_index]){
				temp[temp_index] = A[first_index]; 
				first_index++;
			}
			else{
				//인덱스 최대값이 작은 값에 해당하므로, inversion이 존재하는 경우
				/* 예를들어
				 * [    4,   5,    2,    3]
				 * [left part | right part]
				 * first_index가 현재 1이고, second_index가 3이고, mid가 2이면
				 * 여기서 필요한것은 2입니다. 그렇기 때문에 4,5를 inversion하지 않고 2로 접근해야합니다.	
				 * 
				 * 이후, 왼쪽 부분이 정렬이되고 , 모든 값들은 first_index 시작부터 끝까지 second_index보다 크게 됩니다.
				 * 그리고 그것보다 작은 indexes를 가지는 거죠
				 * 결과적으로 mid - first_index +1 이 출력되는 것입니다.
				 */
				temp[temp_index] = A[second_index];
				second_index ++;
				merge_inver += mid - first_index +1;
				
				if(merge_inver > 1000000000)
					return -1;
			}
			
			temp_index ++;
		}
		// while의 조건을 통해 inversion이 발생할 필요없는 부분을 지나치고
		// 이후 inversion이 발생
		
		// 왼쪽 부분의 값들은 왼쪽에 있는데 그것들은 작은 indexes값을 가지고 있습니다.
		// 하지만 값은 크죠, 즉, inversion이 이루어 져야할 부분입니다.
		// 주의해야할 것은 이러한 inversion횟수는 이미 계산되었습니다.
		if(first_index != mid+1){
			while(first_index <= mid){
				temp[temp_index] = A[first_index];
				first_index ++;
				temp_index ++;
			}
		}
		
		// 오른쪽 부분의 값들은 오른쪽에 있고, 이것들은 왼쪽의 값과 인덱스보다 높은 indexes와 값을 가지고 있습니다.
		// 즉, inversion이 이루어지면 안되는 부분입니다.
		if(second_index != last+1){
			
			while(second_index <= last){
				temp[temp_index] = A[second_index];
				second_index ++;
				temp_index ++;
			}
		}
		
		// temp 배열에 넣었던 값들을 다시 A배열로 옮깁니다.
		A = temp.clone();
		
		if(merge_inver + left_inver + right_inver > 1000000000)
			return -1;
		else
			return merge_inver + left_inver + right_inver;
	}
}

// you can also use imports, for example:
// import java.util.*;

// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    int [] global_A;
    public int solution(int[] A) {
        // write your code in Java SE 8
        global_A = A.clone();
        return mergesort(global_A, 0, global_A.length-1);
    }
    
    public int mergesort(int[]A, int first, int last){
		int mid = (first+last)/2;
		int left_inver, right_inver;
		if(first < last){
			//Recursive calling
			left_inver = mergesort(A, first, mid);
			if(left_inver == -1)
				return -1;
			
			right_inver = mergesort(A, mid+1, last);
			if(right_inver == -1)
				return -1;
		}
		else{ // Terminate condition
			return 0;
		}
		
		int first_index = first; // 왼쪽 부분값의 인덱스
		int second_index = mid+1; // 오른쪽 부분의 인덱스
		
		int[] temp = new int[last-first+1];
		int temp_index = 0;
		int merge_inver = 0; // inversion한 횟수
		
		//왼쪽 인덱스의 위치가 mid보다 작고 오른쪽 인덱스 위치가 last보다 작을때까지 반복
		while(first_index <= mid && second_index <= last){
			
			// P < Q 에 해당하지 않기 때문에 inversion이 이루어 지지 않는 조합
			if(A[first_index] <= A[second_index]){
				temp[temp_index] = A[first_index]; 
				first_index++;
			}
			else{
				//인덱스 최대값이 작은 값에 해당하므로, inversion이 존재하는 경우
				/* 예를들어
				 * [    4,   5,    2,    3]
				 * [left part | right part]
				 * first_index가 현재 1이고, second_index가 3이고, mid가 2이면
				 * 여기서 필요한것은 2입니다. 그렇기 때문에 4,5를 inversion하지 않고 2로 접근해야합니다.	
				 * 
				 * 이후, 왼쪽 부분이 정렬이되고 , 모든 값들은 first_index 시작부터 끝까지 second_index보다 크게 됩니다.
				 * 그리고 그것보다 작은 indexes를 가지는 거죠
				 * 결과적으로 mid - first_index +1 이 출력되는 것입니다.
				 */
				temp[temp_index] = A[second_index];
				second_index ++;
				merge_inver += mid - first_index +1;
				
				if(merge_inver > 1000000000)
					return -1;
			}
			
			temp_index ++;
		}
		// while의 조건을 통해 inversion이 발생할 필요없는 부분을 지나치고
		// 이후 inversion이 발생
		
		// 왼쪽 부분의 값들은 왼쪽에 있는데 그것들은 작은 indexes값을 가지고 있습니다.
		// 하지만 값은 크죠, 즉, inversion이 이루어 져야할 부분입니다.
		// 주의해야할 것은 이러한 inversion횟수는 이미 계산되었습니다.
		if(first_index != mid+1){
			while(first_index <= mid){
				temp[temp_index] = A[first_index];
				first_index ++;
				temp_index ++;
			}
		}
		
		// 오른쪽 부분의 값들은 오른쪽에 있고, 이것들은 왼쪽의 값과 인덱스보다 높은 indexes와 값을 가지고 있습니다.
		// 즉, inversion이 이루어지면 안되는 부분입니다.
		if(second_index != last+1){
			
			while(second_index <= last){
				temp[temp_index] = A[second_index];
				second_index ++;
				temp_index ++;
			}
		}
		
		// temp 배열에 넣었던 값들을 다시 A배열로 옮깁니다.
		int copy_index = first;
		for(int i=0; i <temp_index; i++){
		    A[copy_index] = temp[i];
		    copy_index++;
		}
		
		if(merge_inver + left_inver + right_inver > 1000000000)
			return -1;
		else
			return merge_inver + left_inver + right_inver;
	}
	
	public static void main(String args[]){
		Distinct d = new Distinct();
		
		int [] A ={-1, 6, 3, 4, 7, 4};
		System.out.println(d.solution(A));

	}
}

// you can also use imports, for example:
// import java.util.*;

// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    int [] global_A;
    public int solution(int[] A) {
        // write your code in Java SE 8
        global_A = A.clone();
        return mergesort(global_A, 0, global_A.length-1);
    }
    
    public int mergesort(int[]A, int first, int last){
		int mid = (first+last)/2;
		int left_inver, right_inver;
		if(first < last){
			//Recursive calling
			left_inver = mergesort(A, first, mid);
			if(left_inver == -1)
				return -1;
			
			right_inver = mergesort(A, mid+1, last);
			if(right_inver == -1)
				return -1;
		}
		else{ // Terminate condition
			return 0;
		}
		
		int first_index = first; // 왼쪽 부분값의 인덱스
		int second_index = mid+1; // 오른쪽 부분의 인덱스
		
		int[] temp = new int[last-first+1];
		int temp_index = 0;
		int merge_inver = 0; // inversion한 횟수
		
		//왼쪽 인덱스의 위치가 mid보다 작고 오른쪽 인덱스 위치가 last보다 작을때까지 반복
		while(first_index <= mid && second_index <= last){
			
			// P < Q 에 해당하지 않기 때문에 inversion이 이루어 지지 않는 조합
			if(A[first_index] <= A[second_index]){
				temp[temp_index] = A[first_index]; 
				first_index++;
			}
			else{
				//인덱스 최대값이 작은 값에 해당하므로, inversion이 존재하는 경우
				/* 예를들어
				 * [    4,   5,    2,    3]
				 * [left part | right part]
				 * first_index가 현재 1이고, second_index가 3이고, mid가 2이면
				 * 여기서 필요한것은 2입니다. 그렇기 때문에 4,5를 inversion하지 않고 2로 접근해야합니다.	
				 * 
				 * 이후, 왼쪽 부분이 정렬이되고 , 모든 값들은 first_index 시작부터 끝까지 second_index보다 크게 됩니다.
				 * 그리고 그것보다 작은 indexes를 가지는 거죠
				 * 결과적으로 mid - first_index +1 이 출력되는 것입니다.
				 */
				temp[temp_index] = A[second_index];
				second_index ++;
				merge_inver += mid - first_index +1;
				
				if(merge_inver > 1000000000)
					return -1;
			}
			
			temp_index ++;
		}
		// while의 조건을 통해 inversion이 발생할 필요없는 부분을 지나치고
		// 이후 inversion이 발생
		
		// 왼쪽 부분의 값들은 왼쪽에 있는데 그것들은 작은 indexes값을 가지고 있습니다.
		// 하지만 값은 크죠, 즉, inversion이 이루어 져야할 부분입니다.
		// 주의해야할 것은 이러한 inversion횟수는 이미 계산되었습니다.
		if(first_index != mid+1){
			while(first_index <= mid){
				temp[temp_index] = A[first_index];
				first_index ++;
				temp_index ++;
			}
		}
		
		// 오른쪽 부분의 값들은 오른쪽에 있고, 이것들은 왼쪽의 값과 인덱스보다 높은 indexes와 값을 가지고 있습니다.
		// 즉, inversion이 이루어지면 안되는 부분입니다.
		if(second_index != last+1){
			
			while(second_index <= last){
				temp[temp_index] = A[second_index];
				second_index ++;
				temp_index ++;
			}
		}
		
		// temp 배열에 넣었던 값들을 다시 A배열로 옮깁니다.
		int copy_index = first;
		for(int i=0; i <temp_index; i++){
		    A[copy_index] = temp[i];
		    copy_index++;
		}
		
		if(merge_inver + left_inver + right_inver > 1000000000)
			return -1;
		else
			return merge_inver + left_inver + right_inver;
	}
	
}

// you can also use imports, for example:
// import java.util.*;

// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    int [] global_A;
    public int solution(int[] A) {
        // write your code in Java SE 8
        global_A = A.clone();
        return mergesort(global_A, 0, global_A.length-1);
    }
    
    public int mergesort(int[]A, int first, int last){
		int mid = (first+last)/2;
		int left_inver, right_inver;
		if(first < last){
			//Recursive calling
			left_inver = mergesort(A, first, mid);
			if(left_inver == -1)
				return -1;
			
			right_inver = mergesort(A, mid+1, last);
			if(right_inver == -1)
				return -1;
		}
		else{ // Terminate condition
			return 0;
		}
		
		int first_index = first; // 왼쪽 부분값의 인덱스
		int second_index = mid+1; // 오른쪽 부분의 인덱스
		
		int[] temp = new int[last-first+1];
		int temp_index = 0;
		int merge_inver = 0; // inversion한 횟수
		
		//왼쪽 인덱스의 위치가 mid보다 작고 오른쪽 인덱스 위치가 last보다 작을때까지 반복
		while(first_index <= mid && second_index <= last){
			
			// P < Q 에 해당하지 않기 때문에 inversion이 이루어 지지 않는 조합
			if(A[first_index] <= A[second_index]){
				temp[temp_index] = A[first_index]; 
				first_index++;
			}
			else{
				//인덱스 최대값이 작은 값에 해당하므로, inversion이 존재하는 경우
				/* 예를들어
				 * [    4,   5,    2,    3]
				 * [left part | right part]
				 * first_index가 현재 1이고, second_index가 3이고, mid가 2이면
				 * 여기서 필요한것은 2입니다. 그렇기 때문에 4,5를 inversion하지 않고 2로 접근해야합니다.	
				 * 
				 * 이후, 왼쪽 부분이 정렬이되고 , 모든 값들은 first_index 시작부터 끝까지 second_index보다 크게 됩니다.
				 * 그리고 그것보다 작은 indexes를 가지는 거죠
				 * 결과적으로 mid - first_index +1 이 출력되는 것입니다.
				 */
				temp[temp_index] = A[second_index];
				second_index ++;
				merge_inver += mid - first_index +1;
				
				if(merge_inver > 1000000000)
					return -1;
			}
			
			temp_index ++;
		}
		// while의 조건을 통해 inversion이 발생할 필요없는 부분을 지나치고
		// 이후 inversion이 발생
		
		// 왼쪽 부분의 값들은 왼쪽에 있는데 그것들은 작은 indexes값을 가지고 있습니다.
		// 하지만 값은 크죠, 즉, inversion이 이루어 져야할 부분입니다.
		// 주의해야할 것은 이러한 inversion횟수는 이미 계산되었습니다.
		if(first_index != mid+1){
			while(first_index <= mid){
				temp[temp_index] = A[first_index];
				first_index ++;
				temp_index ++;
			}
		}
		
		// 오른쪽 부분의 값들은 오른쪽에 있고, 이것들은 왼쪽의 값과 인덱스보다 높은 indexes와 값을 가지고 있습니다.
		// 즉, inversion이 이루어지면 안되는 부분입니다.
		if(second_index != last+1){
			
			while(second_index <= last){
				temp[temp_index] = A[second_index];
				second_index ++;
				temp_index ++;
			}
		}
		
		// temp 배열에 넣었던 값들을 다시 A배열로 옮깁니다.
		int copy_index = first;
		for(int i=0; i <temp_index; i++){
		    A[copy_index] = temp[i];
		    copy_index++;
		}
		
		if(merge_inver + left_inver + right_inver > 1000000000)
			return -1;
		else
			return merge_inver + left_inver + right_inver;
	}
	
}

// you can also use imports, for example:
// import java.util.*;

// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    int [] global_A;
    public int solution(int[] A) {
        // write your code in Java SE 8
        global_A = A.clone();
        return mergesort(global_A, 0, global_A.length-1);
    }
    
    public int mergesort(int[]A, int first, int last){
		int mid = (first+last)/2;
		int left_inver, right_inver;
		if(first < last){
			//Recursive calling
			left_inver = mergesort(A, first, mid);
			if(left_inver == -1)
				return -1;
			
			right_inver = mergesort(A, mid+1, last);
			if(right_inver == -1)
				return -1;
		}
		else{ // Terminate condition
			return 0;
		}
		
		int first_index = first; // 왼쪽 부분값의 인덱스
		int second_index = mid+1; // 오른쪽 부분의 인덱스
		
		int[] temp = new int[last-first+1];
		int temp_index = 0;
		int merge_inver = 0; // inversion한 횟수
		
		//왼쪽 인덱스의 위치가 mid보다 작고 오른쪽 인덱스 위치가 last보다 작을때까지 반복
		while(first_index <= mid && second_index <= last){
			
			// P < Q 에 해당하지 않기 때문에 inversion이 이루어 지지 않는 조합
			if(A[first_index] <= A[second_index]){
				temp[temp_index] = A[first_index]; 
				first_index++;
			}
			else{
				//인덱스 최대값이 작은 값에 해당하므로, inversion이 존재하는 경우
				/* 예를들어
				 * [    4,   5,    2,    3]
				 * [left part | right part]
				 * first_index가 현재 1이고, second_index가 3이고, mid가 2이면
				 * 여기서 필요한것은 2입니다. 그렇기 때문에 4,5를 inversion하지 않고 2로 접근해야합니다.	
				 * 
				 * 이후, 왼쪽 부분이 정렬이되고 , 모든 값들은 first_index 시작부터 끝까지 second_index보다 크게 됩니다.
				 * 그리고 그것보다 작은 indexes를 가지는 거죠
				 * 결과적으로 mid - first_index +1 이 출력되는 것입니다.
				 */
				temp[temp_index] = A[second_index];
				second_index ++;
				merge_inver += mid - first_index +1;
				
				if(merge_inver > 1000000000)
					return -1;
			}
			
			temp_index ++;
		}
		// while의 조건을 통해 inversion이 발생할 필요없는 부분을 지나치고
		// 이후 inversion이 발생
		
		// 왼쪽 부분의 값들은 왼쪽에 있는데 그것들은 작은 indexes값을 가지고 있습니다.
		// 하지만 값은 크죠, 즉, inversion이 이루어 져야할 부분입니다.
		// 주의해야할 것은 이러한 inversion횟수는 이미 계산되었습니다.
		if(first_index != mid+1){
			while(first_index <= mid){
				temp[temp_index] = A[first_index];
				first_index ++;
				temp_index ++;
			}
		}
		
		// 오른쪽 부분의 값들은 오른쪽에 있고, 이것들은 왼쪽의 값과 인덱스보다 높은 indexes와 값을 가지고 있습니다.
		// 즉, inversion이 이루어지면 안되는 부분입니다.
		if(second_index != last+1){
			
			while(second_index <= last){
				temp[temp_index] = A[second_index];
				second_index ++;
				temp_index ++;
			}
		}
		
		// temp 배열에 넣었던 값들을 다시 A배열로 옮깁니다.
		int copy_index = first;
		for(int i=0; i <temp_index; i++){
		    A[copy_index] = temp[i];
		    copy_index++;
		}
		
		if(merge_inver + left_inver + right_inver > 1000000000)
			return -1;
		else
			return merge_inver + left_inver + right_inver;
	}
	
}