Read 600,000 input from the console in less than 2 seconds

The Goal

I'm solving this problem:

Little Girl and Maximum Sum

The little girl loves the problems on array queries very much.

One day she came across a rather well-known problem: you've got an array of n elements (the elements of the array are indexed starting from 1); also, there are q queries, each one is defined by a pair of integers li, ri (1 ≤ li ≤ ri ≤ n). You need to find for each query the sum of elements of the array with indexes from li to ri, inclusive.

The little girl found the problem rather boring. She decided to reorder the array elements before replying to the queries in a way that makes the sum of query replies maximum possible. Your task is to find the value of this maximum sum.

Input The first line contains two space-separated integers n (1 ≤ n ≤ 2·105) and q (1 ≤ q ≤ 2·105) — the number of elements in the array and the number of queries, correspondingly.

The next line contains n space-separated integers ai (1 ≤ ai ≤ 2·105) — the array elements.

Each of the following q lines contains two space-separated integers li and ri (1 ≤ li ≤ ri ≤ n) — the i-th query.

Output In a single line print a single integer — the maximum sum of query replies after the array elements are reordered.

With test 7 (see the test results in the end of the question), the input is an array of size 200,000 with 200,000 queries (which have r and l values).

The input looks like this:

200000 200000
189622 189286 194361 184457 182376 183471 197548 184736 195806 ... 200,000 integers

188738 290041
33738 90041
122738 390041
... 200,000 line

You can download a sample input file, or you can create your own sample input. It wouldn't matter the numbers itself.

---

The Problem

I need to read 600,000 input lines without exceeding 2 seconds of execution time. The problem is, it doesn't even read the first 200,000 input in 2 seconds.

How can I speed up my code to read all 600,000 input within 2 seconds?

---

The Code

Here is my first attempt:

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int q = scanner.nextInt();
        int[] array = new int[n];
        for (int i=0; i<n; i++) {
            array[i] = scanner.nextInt();
        }
        int[][] qArray = new int[q][2];
        for (int i=0; i<q; i++) {
            qArray[i][0] = scanner.nextInt();
            qArray[i][1] = scanner.nextInt();
        }

        int[] index = new int[n];
        Arrays.sort(array);
        for (int i=0; i<q; i++) {
            for (int j = qArray[i][0]-1; j<qArray[i][1]; j++) {
                index[j]++;
            }
        }
        Arrays.sort(index);
        long sum =0;
        for (int i = 0; i<n; i++) {
            sum += index[i]*array[i];
        }
        System.out.println(sum);
    }
}

Here is my second attempt:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {

    public static void main(String[] args) {
        try {
            BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
            String input = bufferedReader.readLine();
            String[] SplitInput = input.split(" ");
            int n = Integer.parseInt(SplitInput[0]);
            int q = Integer.parseInt(SplitInput[1]);

            String input2 = bufferedReader.readLine();

            int[][] qArray = new int[q][2];
            for (int i=0; i<q; i++) {
                input = bufferedReader.readLine();
                SplitInput = input.split(" ");
                qArray[i][0] = Integer.parseInt(SplitInput[0]);
                qArray[i][1] = Integer.parseInt(SplitInput[1]);
            }

            String[] SplitInput2 = input2.split(" ");
            int[] array = new int[n];
            for(int i=0; i<n; i++){
                array[i] = Integer.parseInt(SplitInput2[i]);
            }

            int[] index = new int[n];
            Arrays.sort(array);
            for (int i=0; i<q; i++) {
                for (int j = qArray[i][0]-1; j<qArray[i][1]; j++) {
                    index[j]++;
                }
            }
            Arrays.sort(index);
            long sum = 0;
            for (int i=0; i<n; i++) {
                sum += index[i]*array[i];
            }
            System.out.println(sum);
        }
        catch (NumberFormatException ex) {
            System.out.println("Not a number !");
        }
        catch (IOException e) {
            e.printStackTrace();
        }
    }
}

---

Test Results

Attempt 1

7 Time: 2000 ms, memory: 20612 KB Verdict: TIME_LIMIT_EXCEEDED

Attempt 2

7 Time: 2000 ms, memory: 41340 KB Verdict: TIME_LIMIT_EXCEEDED

You can view my full test results here and here. Again, the problem is on Test 7.