시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
20 초 1024 MB 0 0 0 0.000%

문제

You are given an array with $n$ pairwise different values: $A = [a_0, a_1, \dots, a_{n-1}]$. We define the sorted subarray of $A$ starting at $l$ and ending at $r$ as the array that we obtain after sorting $[a_l, a_{l+1}, \dots, a_r]$. For example, if we are given the array $[0,2,14,6,8,10]$, the sorted subarray starting at $1$ and ending at $4$ would be the array that we would get after sorting $[2,14,6,8]$, that is, the array $[2,6,8,14]$.

You are given $q$ queries, each one consists of two integers, $l$ and $r$. For each query, print the sum of the values in the even positions of the sorted subarray of $A$ starting at $l$ and ending at $r$. Here, we assume that all arrays are indexed starting from $0$.

For example, consider the array $[0,2,14,6,8,10]$ and the query $(1,4)$. The subarray starting at $1$ and ending at $4$ is just the array $[2,14,6,8]$. Thus, the sorted subarray starting at $1$ and ending at $4$ is the array $[2,6,8,14]$. Now we have to sum the values in even positions, that is, $2+8 = 10$.

Print the answers modulo $10^9 + 7$.

입력

The first line contains two integers $n$ and $q$ ($1 \leq n \leq 5 \cdot 10^4$; $1 \leq q \leq 2 \cdot 10^5$): the number of elements in the array and the number of queries.

The second line contains $n$ integers $a_0, a_1, \dots, a_{n-1}$ ($0 \leq a_i \leq 10^9$; $a_i$ are pairwise different), the elements of the array.

Finally, each of the next $q$ lines contains two integers $l$ and $r$ ($0 \leq l \leq r < n$): the starting and ending points of the sorted subarray we are considering.

출력

For each query, print a line with the sum of the elements in even positions of the sorted subarray starting at $l$ and ending at $r$ modulo $10^9 + 7$.

예제 입력 1

5 5
2 4 10 16 6
0 2
1 3
0 3
2 3
0 4


예제 출력 1

12
20
12
10
24


예제 입력 2

8 8
38 20 76 96 74 18 66 92
0 5
3 6
1 2
2 7
0 6
2 2
1 6
5 5


예제 출력 2

132
92
20
184
226
76
160
18