King of Range

题号：NC222409
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

Given $n_{}$ integers $a_1,a_2,\cdots,a_n$ 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 $a_l,a_{l+1},\cdots,a_r$ 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 , denoting the number of given integers and the number of queries respectively.

The second line contains n integers , denoting the given integers.

Next m lines each contains one integer , denoting the queries.

输出描述:

Print  lines each contains one integer, denoting the answers.

示例1

输入

复制

5 1
1 2 3 4 5
2

输出

复制

说明

There are three pairs, , which meet the condition.