public class Solution {
public int solve(int[] A) {
return ip(A, 0, A.length - 1);
}
public int ip(int[] arr, int l, int r){
if(l == r){
return 0;
}
int mid = (l + r) / 2;
long f1 = ip(arr, l, mid);
long f2 = ip(arr, mid + 1, r);
long f3 = merge(arr, l, mid + 1, r);
return (int)((f1 + f2 + f3) % 1000000007);
}
public long merge(int[] arr, int l, int y, int r){
//subarray from l to y - 1 is sorted and subarray from y to r is sorted
int[] res = new int[r - l + 1];
int i = l, j = y, k = 0;
long ip = 0;
while(i < y && j <= r){
if(arr[i] <= arr[j]){
res[k] = arr[i];
i++;
k++;
}else{
res[k] = arr[j];
j++;
k++;
ip = ip + (y - i);
}
}
while(i < y){
res[k] = arr[i];
i++;
k++;
}
while(j <= r){
res[k] = arr[j];
j++;
k++;
}
k = 0;
for(i = l ; i <= r; i++){
arr[i] = res[k];
k++;
}
return ip;
}
}