KQUERY Truy vấn K

Cho một dãy n phần tử a₁, a₂, ..., a_n và một số các truy vấn-k. Một truy vấn-k là một bộ ba (i, j, k) (1 ≤ i ≤ j ≤ n). Với mỗi truy vấn-k (i, j, k), bạn phải trả về số phần tử lớn hơn k nằm trong dãy con a_i, a_i+1, ..., a_j.

Input

• Dòng 1: n (1 ≤ n ≤ 30000).
• Dòng 2: n số a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁹).
• Dòng 3: q (1 ≤ q ≤ 200000), số truy vấn-k.
• Trong q dòng tiếp theo, mỗi dòng chứa 3 số i, j, k thể hiện một truy vấn-k (1 ≤ i ≤ j ≤ n, 1 ≤ k ≤ 10⁹).

Output: Với mỗi truy vấn-k (i, j, k), in ra số phần tử lớn hơn k trong dãy con a_i, a_i+1, ..., a_j trên một dòng.

Input	Output
5 5 1 2 3 4 3 2 4 1 4 4 4 1 5 2	2 0 3