D. Strange Queries
time limit per test
3 seconds
memory limit per test
256 megabytes
input
stdin
output
stdout

You are given an array with n integers a1, a2, ..., an, 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

The first line of the input contains an integer n (1 ≤ n ≤ 50 000) — the size of the given array.

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ n).

The third line contains an integer q (1 ≤ q ≤ 50 000) — the number of queries.

Each of the next q lines contains four integers l1, r1, l2, r2 (1 ≤ l1 ≤ r1 ≤ n, 1 ≤ l2 ≤ r2 ≤ n), describing one query.

Output

For each query count the number of sought pairs of indices (i, j) and print it in a separate line.

Examples
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
Output
1
2
5
6
6
2
2
0