区间与绝对值
题号：NC260786
时间限制：C/C++/Rust/Pascal 4秒，其他语言8秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

给定一个长度为 n 的序列 a，序列 a 的第 i 个数为 a_i。

给定 m 次询问，每次询问给出一个区间，其中第 k 个区间是[l_k, r_k]，每次询问\sum_{i = l_k}^{r_k} \sum_{j = l_k}^{r_k} |a_i-a_j|。

输入描述:

第一行两个正整数 n, m(1 \leq n,m\leq 100000 )，表示序列 a (1 \leq a_i \leq 100000)的长度和询问的次数。 

接下来的一行，共 n 个整数，第 i 个整数表示a_i。

接下来的 m 行，每行两个正整数l_k, r_k (1 \leq l_l \leq r_k \leq n)，表示询问\sum_{i = l_k}^{r_k} \sum_{j = l_k}^{r_k} |a_i-a_j|。 

输出描述:

一共有m行，其中第 k 行输出\sum_{i = l_k}^{r_k} \sum_{j = l_k}^{r_k} |a_i-a_j|。
示例1

输入

复制 
10 10
3 1 10 3 1 4 1 9 8 2
4 8
2 8
1 4
3 5
3 6
7 9
2 6
2 7
3 5
5 9

输出

复制 
76
184
54
36
56
32
84
112
36
92