Limits
1s, 512 MB

Suppose you have a multiset of numbers $\lbrace a_1, a_2, \dots, a_k \rbrace$. Suppose $x$ is the smallest number and $y$ is the largest number in the set. In each move, you can remove $x$ and $y$ from the set and add $2xy - x - y + 1$ instead. So in each step, size of the set decreases by one. After $k - 1$ moves are performed, you have only one number remaining in the set. Let's call this number survivor of the set.

The value of a set is defined as the sum of survivors of all non-empty subsets of it.

In this problem, you have an array $b_1, b_2, b_3, \dots, b_n$ where $1 \leq n \leq 10^{5}$ and $1 \leq b_i \leq 10^{9}$. You have answer $q \, (1 \leq q \leq 10^{5})$ queries of this format: given $l$ and $r$, what is the value of the set containing $\lbrace b_l, b_{l + 1}, b_{l + 2}, \dots, b_r \rbrace$? Since the value can be extremely large, output the answer modulo ${10^9 + 7}$.

First line contains the value of $n$ ($1 \leq n \leq 100000$).

Second line contains $n$ integers. $i$-th integer of this line represents the value of $b_i$.

Third line contains the value of $q$ ($1 \leq q \leq 100000$).

Next $q$ lines contain two integers $l$ and $r$, representing the parameters of the query.

Output $q$ lines: $i$-th line contains the answer for the $i$-th query.

Input | Output |
---|---|

5 3 4 1 5 6 3 1 5 1 1 3 4 | 5775 3 11 |

In the third query, the set is $\lbrace 1, 5 \rbrace$. So the subsets are $\lbrace 1 \rbrace$, $\lbrace 5 \rbrace$ and $\lbrace 1, 5 \rbrace$. The survivors are 1, 5 and 5 respectively, which adds up to 11. |

The difference between a set and a multiset is that unlike set, multiset can contain same element more than once. For sake of clarity, every mention of a set indigates a multiset in this problem.

Login to submit.

20%
Solution Ratio

fsshakkhorEarliest,

fsshakkhorFastest, 0.2s

fsshakkhorLightest, 2.6 MB

fsshakkhorShortest, 2737B

Toph uses cookies. By continuing you agree to our Cookie Policy.