403356: GYM101138 D Strange Queries

You are given an array with n integers a₁, a₂, ..., a_n, and q queries to answer.

Each query consists of four integers l₁, r₁, l₂ and r₂. Your task is to count the number of pairs of indices (i, j) satisfying the following conditions:

1. a_i = a_j
2. l₁ ≤ i ≤ r₁
3. l₂ ≤ j ≤ r₂

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 a₁, a₂, ..., a_n (1 ≤ a_i ≤ 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 l₁, r₁, l₂, r₂ (1 ≤ l₁ ≤ r₁ ≤ n, 1 ≤ l₂ ≤ r₂ ≤ n), describing one query.

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

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

1
2
5
6
6
2
2
0