Đếm Phần Tử Vượt Ngưỡng

Cho một mảng cố định. Mỗi truy vấn ($l,r,k$) hỏi số phần tử lớn hơn $k$ trong đoạn chỉ số từ $l$ đến $r$.

Input

• Dòng đầu chứa $n$.
• Dòng thứ hai chứa $n$ số $a_1,\dots ,a_n$.
• Dòng thứ ba chứa $q$.
• Mỗi trong $q$ dòng tiếp theo chứa $l,r,k$.

Output

• Với mỗi truy vấn, in đáp án trên một dòng theo đúng thứ tự xuất hiện.

Constraints

• $1\le n\le 3\cdot 10^4$.
• $1\le a_i\le 10^9$.
• $1\le q\le 2\cdot 10^5$.
• $1\le l\le r\le n$.
• $1\le k\le 10^9$.

Scoring

• Subtask $1$ ($50\%$ số điểm): $n\le 100$ và $q\le 100$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

6
4 1 7 4 9 2
4
1 6 4
2 5 3
3 3 7
4 6 1

2
3
0
3