Pairwise Product#251
You are given an array of integers a_1,a_2,\dots,a_n. Your task is to answer queries of the following type:
For given , output the sum of products for all pairs l\le i<j\le r. Formally, you need to compute \sum\limits_{l\le i<j\le r}a_i\cdot a_j. The answer may be large, so output it modulo 10^9+7.
The first line contains a single number (2\le n\le 2\cdot 10^5) — the size of the array .
The second line contains integers a_1,\dots,a_n (1\le a_i\le 10^9) — the elements of the array.
The third line contains a single integer (1\le q\le 2\cdot 10^5) — the number of queries.
Each of the next lines contains two integers and (1\le l<r\le n).
Output lines — the answer to each query.
Example
Example 1
Example 2
In this problem, there are conditional blocks. If your solution works correctly for certain constraints, it will receive a certain number of points. Please note that the evaluation is still in the testing phase.
( points): n\le 100, q\le100;
( points): n\le 10\,000, q\le 100;
( points): without additional constraints.