Problem Description

You are given a sequence $a_i$ of length $N$, where $1\leq i\leq N$, and $q$ queries. For each query, you are given $l_1,r_1,l_2,r_2$, and you need to output

$$\sum\limits_{x=0}^\infty \text{get}(l_1,r_1,x)\times \text{get}(l_2,r_2,x)$$

Here, $\text{get}(l,r,x)$ means the number of times the value $x$ appears in the interval $[l,r]$.

Input Format

The first line contains an integer $N$, the length of the sequence.
The second line contains $N$ integers, representing $a_1\sim a_N$.
The third line contains an integer $Q$, the number of queries.
Lines $4$ to $Q+3$ each contain four integers $l_1,r_1,l_2,r_2$, representing a query.

Output Format

For each query, output one integer per line, representing the answer.

5
1 1 1 1 1
2
1 2 3 4
1 1 4 4

4
1

Hint

For $20\%$ of the testdata, $1\leq N,Q\leq 1000$.
For another $30\%$ of the testdata, $1\leq a_i\leq 50$.
For $100\%$ of the testdata, $N,Q\leq 50000$, $1\leq a_i\leq N$, $1\leq l_1\leq r_1\leq N$, $1\leq l_2\leq r_2\leq N$.

The Constraints are the same as the original problem, but the testdata is made by LibreOJ and is not the original testdata.

Note: The answer may exceed the maximum value of int.

Translated by ChatGPT 5