\begin{problem}{Pairwise Product}{standard input}{standard output}{3 seconds}{256 megabytes}

You are given an array of integers $a_1,a_2,\dots,a_n$. Your task is to answer queries of the following type:

\begin{itemize}
\item For given $l,r$, 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$.
\end{itemize}

\InputFile
The first line contains a single number $n$ ($2\le n\le 2\cdot 10^5$)~--- the size of the array $a$.

The second line contains $n$ 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 $q$ ($1\le q\le 2\cdot 10^5$)~--- the number of queries.

Each of the next $q$ lines contains two integers $l$ and $r$ ($1\le l<r\le n$).

\OutputFile
Output $q$ lines~--- the answer to each query.

\Scoring
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.

\begin{enumerate}
\item ($29$ points): $n\le 100$, $q\le100$;
\item ($36$ points): $n\le 10\,000$, $q\le 100$;
\item ($35$ points): without additional constraints.
\end{enumerate}

\Examples

\begin{example}
\exmpfile{example.01}{example.01.a}%
\exmpfile{example.02}{example.02.a}%
\exmpfile{example.03}{example.03.a}%
\end{example}

\end{problem}

