小红有一天拿到了 M 个数组 A[x] (1 <= x <= M)，他用这个数组构造 M 个新数组 B[x]，其中 A[x][i] 代表 B[x] 数组中有 A[x][i] 个 i。例如，若 A[x] = [2,3,1]，那么 B[x] = [1,1,2,2,2,3]。

聪明的小红把这些数组用某种神秘的方法压缩成了一个长度为 N 的数组 C，每个 A[x] 都能用 C 的某个子数组表示，因此，对于每个数组 A[x]， 小红只会给你 A[x] 在 C 数组出现的左边界 L 和右边界 R。

现在给定 C 数组 和 每个 A[x] 在 C 数组中的左边界与右边界，你需要帮小红对每个 1 <= x <= M 分别求出对应 B[x] 数组中所有连续子数组的极差之和。由于答案可能过大，请对 1000000007 取模。数组的极差指数组中的最大值减去数组中的最小值。

第一行有两个正整数 N, M。
第二行有 N 个正整数，表示 C。
后面有 M 行， 每行有两个整数 L, R，按顺序表示 A[x] 在 C 数组出现的左边界和右边界。

输出有 M 行， 每行一个整数，第 x 行 表示 B[x] 数组中所有连续子数组的极差之和。

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

2
7
0
1

A[1] = [2, 1] 时，B[1] 数组为 [1, 1, 2]。
此时 B[1] 数组共有 6 个连续子数组:
[1] 的极差为 0
[1] 的极差为 0
[2] 的极差为 0
[1, 1] 的极差为 0
[1, 2] 的极差为 1
[1, 1, 2] 的极差为 1
因此答案是0 + 0 + 0 + 0 + 1 + 1 = 2
1 <= N, M <= 100000
1 <= C[i] <= 1000000000
1 <= L <= R <= N