8166: K-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 <= 1e5, 1 <= m <= 200), denoting the number of given integers and the number of queries respectively.
The second line contains n integers a1, a2, ... , an(1 <= ai <= 1e9), denoting the given integers.
Next m lines each contains one integer k(1 <= k <= 1e9) , 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.