i-strange-queries

You are given a 1-indexed array A of the length N, and Q queries to answer.

Each query consists of four integers L1, R1, L2 and R2.
Your task is to count the number of pairs of indices (i, j) satisfying the following conditions:
1) Ai = Aj
2) L1 ≤ i ≤ R1
3) L2 ≤ j ≤ R2

Input format
The first line contains one integer N.

The second line contains N space-separated integers A1, A2, ..., AN.

The third line contains one integer Q.

Each of the next Q lines contains four integers L1, R1, L2 and R2, describing one query.

Output format
For each query print the answer in a separate line.

Constraints
1 ≤ N, Q ≤ 50,000
1 ≤ Ai ≤ N
1 ≤ L1 ≤ R1 ≤ N
1 ≤ L2 ≤ R2 ≤ N

SAMPLE INPUT
7
1 5 2 1 7 2 2
8
1 3 4 5
2 3 5 7
1 4 3 7
2 6 4 7
1 6 2 5
3 3 6 7
4 5 1 4
2 3 4 5

SAMPLE OUTPUT
1
2
5
6
6
2
2
0

Source: hackerearth | Difficulty: HARD
Tags: Dynamic programming

Square root algorithms


Solutions: