Cho một dãy ~A~ gồm ~N~ số nguyên ~a_1, a_2, a_3, \ldots, a_N~ đã được sắp xếp tăng dần. Bạn cần trả lời ~Q~ truy vấn sau:

Cho 3 số ~L, R, x~. Có bao nhiêu số có giá trị ~x~ trong dãy con ~a_L, a_{L + 1}, a_{L + 2}, \ldots, a_{R}~?

Input

• Dòng đầu tiên là ~1~ số ~N~ (~N \leq 10^6~).
• Dòng thứ ~2~ gồm ~N~ số của dãy ~A~ (~0 \leq a_{i} \leq 10^9~).
• Dòng thứ ~3~ gồm số ~Q~ (~Q \leq 10^5~).
• ~Q~ dòng tiếp theo mỗi dòng gồm ~3~ số ~l, r, x~. (~0 \leq l \le r \le n - 1~)

Output

• ~Q~ dòng cho biết có bao nhiêu số có giá trị ~x~ trong dãy con ~a_L, a_{L + 1}, a_{L + 2}, \ldots, a_{R}~ ở mỗi truy vấn.

Sample Test

Input:

7
1 2 3 3 4 4 5
2
0 6 5
0 5 4

Output:

1
2