Template: Solution.java (https://we.tl/t-Iq9UoY1cMV)

import java.io.*; import java.util.StringTokenizer; public class Solution { public static int[] computeL(int[] A) { //TODO //Fill up your code here. } // This main() handles the input and output in a fast buffered // way, you DO NOT need to modify main(). public static void main(String[] args) throws IOException { // Read input array A. We avoid java.util.Scanner, for speed. BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); // first line int[] A = new int[N]; StringTokenizer st = new StringTokenizer(br.readLine()); // second line for (int i=0; i 
 
 
 
 
Use the given template above. Just complete method ComputeL. The Big Oh should not be greater than O(N) (It cannot be N log N)
 
 
 
Answer is probably some version of Sedgewick's inversion counting(https://algs4.cs.princeton.edu/22mergesort/Inversions.java.html), with either indirect sorting or pair sorting.
  We have an array A of N values to sort: A[0],A[1],,A[N1] Consider Insertion Sort. For each value A[i] (for i=0,1,2, ), we "insert" it in its correct position among the previous values. The inserted A[i] moves L[i] steps to its left, where L[i] is the number of larger values to its left. Note those larger values were also to its left in the original array. We could compute these L[i] values as a side-effect of insertion sort. However, insertion sort can take quadratic time, which is too slow. Your goal is to compute them by a faster method. Input Format The input is two lines. The first line has a single integer: N The second line has N integers: A[0]A[1]A[N1] Constraints 1N100,000 For each i, 0A[i]