408329: GYM103098 E Even Intervals

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$$$.

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

12
20
12
10
24

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

132
92
20
184
226
76
160
18