SOLVE

LATER

Finding the Subarrays

/

You are given an array \(A\) of \(N\) elements. You need to find all the subarrays such that their average sum is greater than the average sum of the remaining array elements. You need to print the start and end index of each subarray in sorted order in a new line.

**Notes: **

- A subarray which starts at position \(L_1\)and ends at position \(R_1\) comes before a subarray that starts at \(L_2\) and ends at \(R_2\) if \(L_1 \lt L_2\) or if \(L_1 = L_2\) but \(R_1 \le R_2\)
- The array indexes are in the range \(1\) to \(N\) .
- The average sum of an empty array is 0.

**Input**

The first line contains an integer \(N\) that denotes the total number of elements in the array.

The next line contains \(N\) space separated integers that denote the elements of the array \(A\) .

**Output**

The first line of output should contain an integer \(X\) that denotes how many subarrays that follow the given criterion are there.

The next \(X\) lines contain a pair of space-separated integers corresponding to the start and end positions of the valid subarrays.

**Constraints**

\(1 \le N \le 2000 \)

\(1 \le A[i] \le 10^6\)

Explanation

The average of subarray \([1,2]\) is - \((3 + 4) / 2 = 3.5\) , the average of remaining element is \(2/1 = 2\) , thus it is a valid subarray

The average of subarray \([1,3]\) is - \((9) / 3 = 3\) , the average of remaining element is \(0\) , thus it is a valid subarray

The average of subarray \([2,2]\) is - \((4) / 1 = 4\), the average of remaining element is \((3 + 2)/2 = 2.5\) , thus it is a valid subarray

Time Limit:
3.0 sec(s)
for each input file.

Memory Limit:
256 MB

Source Limit:
1024 KB

Initializing Code Editor...