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 翻译