5001: Lipshitz Sequence
内存限制：256 MB
时间限制：2 S
标准输入输出
题目类型：传统
评测方式：文本比较
上传者：
提交：1
通过：1
题目描述
B. Lipshitz Sequence
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
A function 
is called Lipschitz continuous if there is a real constant K such that the inequality |f(x)-f(y)|≤K·|x-y| holds for all 
. We'll deal with a more... discrete version of this term.
For an array
, we define it's Lipschitz constant 
as follows:
is the smallest non-negative integer such that |h[i]-h[j]|≤L·|i-j| holds for all 1≤i,j≤n.
You are given an array
of size n and q queries of the form [l,r]. For each query, consider the subarray 
; determine the sum of Lipschitz constants of all subarrays of 
.
is called Lipschitz continuous if there is a real constant K such that the inequality |f(x)-f(y)|≤K·|x-y| holds for all . We'll deal with a more... discrete version of this term. For an array
, we define it's Lipschitz constant as follows: -
if n<2,
-
if n≥2,
over all 1≤i<j≤n
is the smallest non-negative integer such that |h[i]-h[j]|≤L·|i-j| holds for all 1≤i,j≤n. You are given an array
of size n and q queries of the form [l,r]. For each query, consider the subarray ; determine the sum of Lipschitz constants of all subarrays of .
Input
The first line of the input contains two space-separated integers n and q (2≤n≤100000 and 1≤q≤100)− the number of elements in array and the number of queries respectively. The second line contains n space-separated integers
(
). The following q lines describe queries. The i-th of those lines contains two space-separated integers li and ri (1≤li<ri≤n).
Output
Print the answers to all queries in the order in which they are given in the input. For the i-th query, print one line containing a single integer− the sum of Lipschitz constants of all subarrays of 
.
Examples
Input
10 4 1 5 2 9 1 3 4 2 1 7 2 4 3 8 7 10 1 9
Output
17 82 23 210
Input
7 6 5 7 7 4 6 6 2 1 2 2 3 2 6 1 7 4 7 3 5
Output
2 0 22 59 16 8
Note
In the first query of the first sample, the Lipschitz constants of subarrays of 
with length at least 2 are: 
输入样例 复制
输出样例 复制