该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

彩虹求和

题目描述

给定一个长度为 $n$ 的整数数组 $a_1,a_2,\dots,a_n$。

现在有 $q$ 次查询，每次给定一个区间 $[l,r]$，你需要计算这个区间的 拱形加权和。

设区间内的元素依次为：

对于这个区间中的第 $1$ 个数、第 $2$ 个数、第 $3$ 个数……，它们的系数依次为：

而当走到区间右半部分时，系数开始递减，因此整个系数序列呈“拱形”。

形式化地，设区间长度为：

那么第 $i$ 个位置（从 $0$ 开始计）的系数为：

因此该区间的答案为：

你需要回答每次查询的结果。

输入格式

第一行输入两个整数 $n(1\leq n\leq2\times10^5)$ $,q(1\leq q\leq2\times10^5)$，表示数组长度和查询次数。

第二行输入 $n$ 个整数 $a_1,a_2,\dots,a_n(1\leq a_i\leq 10^6)$，表示数组中的元素。

接下来 $q$ 行，每行输入两个整数 $l,r(1\leq l\leq r\leq n)$，表示一次查询区间。

输出格式

对于每次查询，输出一行一个整数，表示对应区间的拱形加权和。

输入输出样例 #1

输入 #1

5 3
1 2 3 4 5
1 5
2 4
3 3

输出 #1

27
12
3