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