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 gồm duy nhất số nguyên ~N~ (~N \leq 10^6~) - kích thước mảng.
• Dòng thứ hai gồm ~N~ số nguyên ~a_i~ (~0 \leq a_i \leq 10^9~).
• Dòng thứ ba gồm số truy vấn ~Q~ (~Q \leq 10^5~) - số truy vấn.
• ~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