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