#P18116. Interval MST

Interval MST

Interval MST

给定整数序列 x1,…,xnx_1,\ldots,x_n。建立顶点为 1,…,n1,\ldots,n 的无向完全图,对每个 u<vu<v,边 {u,v}\{u,v\} 的权值是

xv−xu.x_v-x_u.

数组不保证有序,边权可以为负。注意这不是绝对值。

对区间 [l,r][l,r],仅保留编号属于此区间的顶点及它们之间的边,定义 f(l,r)f(l,r) 为这个诱导子图的最小生成树权值。单点区间规定为0。

给定 qq 个区间,求每个 f(l,r)f(l,r)。

输入格式

第一行两个整数 n,qn,q,1≤n,q≤2000001\le n,q\le200000。

第二行 nn 个整数 xix_i,−109≤xi≤109-10^9\le x_i\le10^9。

接下来 qq 行,每行两个整数 l,rl,r,1≤l≤r≤n1\le l\le r\le n。

输出格式

每个询问输出一行整数答案。

样例

3 4
0 10 0
1 3
1 2
2 3
2 2
-10
10
-10
0

整个图三条边的权为10、0、-10,选择后两条得到最小生成树权-10。