You Are given an array A of N integers. You have to answer Q queries of form L R. Answer to each query is sum of lengths of all sub arrays in A whose maximum element lies in range [L,R].
Constraints:
1<=N,Q<=3*10^5 1<=A[i]<=10^9 1<=L<=R<=10^9
Input: 5 3
1 2 3 4 5
1 3
1 5
5 5
Output:
10 35 15