Survivor Sum

Limits 1s, 512 MB

Suppose you have a multiset of numbers {a1,a2,,ak}\lbrace a_1, a_2, \dots, a_k \rbrace. Suppose xx is the smallest number and yy is the largest number in the set. In each move, you can remove xx and yy from the set and add 2xyxy+12xy - x - y + 1 instead. So in each step, size of the set decreases by one. After k1k - 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 b1,b2,b3,,bnb_1, b_2, b_3, \dots, b_n where 1n1051 \leq n \leq 10^{5} and 1bi1091 \leq b_i \leq 10^{9}. You have answer q(1q105)q \, (1 \leq q \leq 10^{5}) queries of this format: given ll and rr, what is the value of the set containing {bl,bl+1,bl+2,,br}\lbrace b_l, b_{l + 1}, b_{l + 2}, \dots, b_r \rbrace? Since the value can be extremely large, output the answer modulo 109+7{10^9 + 7}.

Input

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

Second line contains nn integers. ii-th integer of this line represents the value of bib_i.

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

Next qq lines contain two integers ll and rr, representing the parameters of the query.

Output

Output qq lines: ii-th line contains the answer for the ii-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 {1,5}\lbrace 1, 5 \rbrace. So the subsets are {1}\lbrace 1 \rbrace, {5}\lbrace 5 \rbrace and {1,5}\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.