问题陈述
对于整数序列 X = (X_1, X_2, \dots, X_k),让我们定义一个函数 f(X) 如下:
- 让 Y = (Y_1, Y_2, \dots, Y_k) 为排序得到的序列 X 按升序排列。
- 然后, \displaystyle f(X) = \sum_{i=1}^{k-1}(Y_{i+1}-Y_i)^2.
我们有一个整数序列 A = (A_1, A_2, \dots, A_N)。 给定 Q 查询如下格式,按顺序处理。
- 给定整数 l 和 r,查找 f(B),其中 B = (A_l, A_{l + 1}, \dots, A_r).
约束
- 输入中的所有值都是整数。
- 1≤N≤2\times10^4
- 1≤A_i≤10^9
- 1≤Q≤10^5
- 对于每个查询, 1≤l≤r≤N.
输入
输入由标准输入按以下格式给出:
N
A_1 A_2 \cdots A_N
Q
\text{Query}_1
\text{Query}_2
\vdots
\text{Query}_Q
在这里, \text{Query}_i 表示 i第一个查询。 每个查询均按以下格式给出:
l r
输出
打印 Q 行。 的 i- 第行应包含以下问题的答案 i第一个查询。
示例输入 1
3 3 1 4 4 1 1 1 2 2 3 1 3
示例输出 1
0 4 9 5
我们有 A = (3, 1, 4).
- 在 1-st 查询, f(B) = 0,因为排序 B = (3) 按收益率升序排列 (3).
- 在 2-nd 查询, f(B) = 4,因为排序 B = (3, 1) 按收益率升序排列 (1, 3).
- 在 3-rd 查询, f(B) = 9,因为排序 B = (1, 4) 按收益率升序排列 (1, 4).
- 在 4第一个查询, f(B) = 5,因为排序 B = (3, 1, 4) 按收益率升序排列 (1, 3, 4).
示例输入 2
10 19 70 14 11 85 75 72 35 14 50 10 1 1 3 8 5 7 1 3 5 8 5 5 2 10 2 5 1 5 2 9
示例输出 2
0 1928 109 2626 1478 0 1188 3370 2860 1788