Repeated Numbers

Problem Description

Given a sequence $A = (a_1, a_2, \dots, a_n)$ and several queries. Each query asks: in the interval $[l_i, r_i]$, how many numbers appear exactly $k_i$ times?

Input Format

The first line contains one integer $n\ (1 \le n \le 10^5)$, the length of the sequence.

The second line contains $n$ integers $a_1, a_2, \dots, a_n\ (1 \le a_i \le 10^5)$, the elements of the sequence.

The third line contains one integer $m\ (1 \le m \le 10^5)$, the number of queries.

The following $m$ lines describe the queries; the $i$-th line contains three integers $l_i, r_i, k_i\ (1 \le l_i < r_i \le n,\ 1 \le k_i \le n)$, asking how many numbers in $[l_i, r_i]$ appear exactly $k_i$ times.

Output Format

Output $m$ lines, each the answer to the corresponding query.

Sample Input

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

Sample Output

1
0
2
0
1