5395: King of Range

Given n integers a1,a2,⋯,an and m queries. For each query, you are given a const k and you should determine how many different pairs (l,r) are there meeting the condition that the range of the subsequence al,al+1,⋯,ar is strictly greater than k .

Note: the range of a sequence equals the difference between the maximum and the minimum of the sequence.

The first line contains two integers n,m(1≤n≤10^5,1≤m≤100), denoting the number of given integers and the number of queries respectively.The second line contains n integers a1,a2,⋯,an(1≤ai≤109) denoting the given integers.
Next m lines each contains one integer k(1≤k≤10^9), denoting the queries.

Print m lines each contains one integer, denoting the answers.

5 1
1 2 3 4 5
2

3

There are three pairs, (1,4),(1,5),(2,5) which meet the condition.