Source : NOI2017贵州省选
Description
给定n个数a1,...,an
对于一组配对(x,y),若对于所有的i = 1,2,… , n,满足|ax-ay| ≤ |ax-ai|,则称(x, y)
为一组好的配对(|x|表示x的绝对值)。
给出若干询问,每次询问区间[l, r]中含有多少组好的配对。
即,取x, y(l ≤ x, y ≤ r且x ≠ y),问有多少组(x, y)是好的配对。
Input
第一行两个正整数n,m。
第二行n个数a1, … , an
接下来m行,每行给出两个数l, r。
Output
Ansi表示第i次询问的答案,输出Ans1 × 1 + Ans2 × 2 + ... + Ansm × m即可
Sample Input
3 2
2 1 3
1 2
1 3
Sample Output
10
Hint
【样例解释】
第一次询问好的配对有:(1,2)(2,1);
第二次询问好的配对有:(1,2)(2,1), (1,3)(3,1);
答案= 2 × 1 + 4 × 2 = 10。