# Survivor Sum

Father Timm Memorial Prog...
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}$.

## Input

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

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

## Sample

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