U140357 Seaway连续

$Seaway$最近正在学习数学的实分析。这一天，他了解到实分析中的这样一种定义：对于在实数集的子集的函数$f:D\subseteq \R \rightarrow \R$ ，若存在常数$K$，使得$|f(a)-f(b)|\le K\times|a-b|,\forall a,b\in D$ ，则称$f$符合**利普希茨条件(Lipshitz Continuous)**，对于$f$最小的常数$K$称为$f$的**利普希茨常数(Lipshitz number)**。

$Seaway$马上对于利普希茨条件产生了极大的兴趣，并对其潜心研究。他觉得$Lipshitz$条件在实分析数学中的确有着非常广泛的意义。但是，同样地，其定义域的广度也造成了它具备一定的困难度。现在，$Seaway$着手对利普希茨条件进行了合理简化，产生了$Seaway$连续(Seaway Continuous)。其定义如下： 对于一个由正整数构成的序列$v[1...n]$，定义其$Seaway$连续$S(v)$为：对于任意整数$i,j\in[1,n]$，满足$|v[j]-v[i]|\le K\times |j-i|$的最小非负整数$K$。 现在，给出一个长度为$n$的序列$v[1...n]$和$q$个询问，对于每个询问$[l,r]$，请你求出：$v[l...r]$的所有子序列的$Seaway$连续值之和。

从文件$continuous.in$中读入数据。 第一行两个整数$n,q$，表示序列长度和询问个数。第二行$n$个数，描述$v$序列。接下来的$q$行，每行两个整数$l,r$，表示每个询问区间为$[l,r]$。

输出到文件$continuous.out$中。 对于每个询问，输出一行一个数$ans$，表示$v[l...r]$的所有子序列的$Seaway$连续之和。

【**样例1解释**】 对于第一个询问，在$[5,2,9]$的所有子区间中： $S([5,2])=3,S([2,9])=7,S([5,2,9])=7$。 所以，答案为$3+7+7=17$。 【**数据范围**】 对于$20\%$的数据，$n=10,q=100$。 对于另$20\%$的数据，$n=100,q=10$。 对于另$20\%$的数据，$n=1000,q=10$。 对于另$20\%$的数据，$n=10000,q=10$。 对于全部数据，$2\le n\le 10^5,1\le q\le 100,0\le v[i]\le 10^9$。