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\)
3 3 4 2
3 1 2 1 3 2 2
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
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor