rt

今日模拟赛题，求原题，想看一下自己是不是最优解。

这应该是一道简单题。

你有一个长度为 n 的序列，第 i 个元素是 a_i。

定义一个区间的权值 val(L,R) 为 a_L × a_R。

q 次询问，每次给出一个区间 [l,r] ，你需要求出来所有满足 l ≤ i ≤ j ≤ r 的 val(i,j) 的和。

第一行共 2 个整数 ( n, q )。

第二行共 ( n ) 个整数，第 ( i ) 个整数表示 ( a_i )。

接下来 ( q ) 行，每行 2 个整数表示 ( l, r )。

输出共 ( q ) 行，第 ( i ) 行共 1 个整数，表示第 ( i ) 次询问的答案。

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

7
19
37
25

考虑第一个样例的第一个询问，注意到求解的形如 ( val(1,1) + val(1,2) + val(2,2) = 1 + 2 + 4 = 7 )。

对于所有测试点满足 ( 1 \leq n,q \leq 10^5, 1 \leq a_i \leq 10^4 )。

每个测试点的具体限制见下表：