SP9569 PAIRSUM - Sum of Pairwise Products

给定 $N$ 个非负整数，需要回答 $M$ 个查询。 每个查询提供一对整数 $u, v$（以零为起始索引），要求计算从 $u$ 到 $v$ 索引之间的元素所形成的所有可能的成对乘积和。具体公式如下： $$ a_u^2 + a_{u+1}^2 + a_{u+1}a_u + a_{u+2}^2 + a_{u+2}a_{u+1} + a_{u+2}a_u + \ldots + a_v^2 + a_v a_{v-1} + \ldots + a_v a_u $$

第一行输入一个整数 $N$，表示非负整数的个数。 第二行输入 $N$ 个整数 $a_0, a_1, \ldots, a_{N-1}$，用空格分隔。 第三行输入一个整数 $M$，表示查询的次数。 接下来 $M$ 行，每行输入两个整数 $u_i$ 和 $v_i$，表示一个查询。

对每个查询，在单独一行输出其答案。 **本翻译由 AI 自动生成**