AT_past202212_n.数列と関数

对于一个整数序列 $X = (X_1, X_2, \dots, X_k)$，定义函数 $f(X)$ 如下：

• 令 $Y = (Y_1, Y_2, \dots, Y_k)$ 为将 $X$ 升序排序后得到的序列。
• 则 $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)$。

输入以如下格式从标准输入中给出：

$N$ $A_1$ $A_2$ $\cdots$ $A_N$ $Q$
$\text{查询}_1$
$\text{查询}_2$
$\vdots$
$\text{查询}_Q$

这里，$\text{查询}_i$ 表示第 $i$ 个查询，每个查询包含以下内容：

$l$ $r$

输出共 $Q$ 行，第 $i$ 行输出第 $i$ 个查询的答案。

样例说明 1

已知 $A = (3, 1, 4)$。

• 第 1 个查询，$f(B) = 0$，因为排序后 $B = (3)$，只有一个元素。
• 第 2 个查询，$f(B) = 4$，因为排序后 $B = (3, 1) = (1, 3)$。
• 第 3 个查询，$f(B) = 9$，因为排序后 $B = (1, 4) = (1, 4)$。
• 第 4 个查询，$f(B) = 5$，因为排序后 $B = (3, 1, 4) = (1, 3, 4)$。

数据范围

• 输入中的所有值均为整数。
• $1 \leq N \leq 2 \times 10^4$
• $1 \leq A_i \leq 10^9$
• $1 \leq Q \leq 10^5$
• 对每个查询，$1 \leq l \leq r \leq N$。

由 ChatGPT 5 翻译