Giải bài trực tuyến

Given a sequence of n numbers a₁, a₂ ... a_n and a number of k-queries. A k-query is a triple (i, j, k) (1 ≤ i ≤ j ≤ n). For each k-query (i, j, k), you have to return the number of elements greater than k in the subsequence a_i, a_i+1 ... a_j.

Input

• Line 1: n (1 ≤ n ≤ 30000).
• Line 2: n numbers a₁, a₂ ... a_n (1 ≤ a_i ≤ 10⁹).
• Line 3: q (1 ≤ q ≤ 200000), the number of k- queries.
• In the next q lines, each line contains 3 numbers i, j, k representing a k-query (1 ≤ i ≤ j ≤ n, 1 ≤ k ≤ 10⁹).

Output

• For each k-query (i, j, k), print the number of elements greater than k in the subsequence a_i, a_i+1 ... a_j in a single line.

Example

Input
5
5 1 2 3 4
3
2 4 1
4 4 4
1 5 2 

Output
2
0
3