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 L1and ends at position R1 comes before a subarray that starts at L2 and ends at R2 if L1<L2 or if L1=L2 but R1≤R2
- 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≤N≤2000
1≤A[i]≤106
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
