This problem is a Mooshak version of a SPOJ problem.

[PC018] K-Query

You will be given a sequence of \(n\) numbers \(a_1, a_2, \ldots, a_n\) and a number of k-queries in the form of a triple of integers \((i, j, k)\). For each of the queries, you have to return the number of elements greater than \(k\) in the subsequence \(a_i, a_{i+1}, \ldots, a_j\).

Input

The first input line contains two integers \(n\) and \(q\): the size of the sequence and the number of queries.

The next line contains \(n\) integers \(a_1, a_2, \ldots, a_n\)​: the integers in the sequence.

The next \(q\) lines each contain a query in the form of three integers \(i \, j \, k\).

Output

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

Constraints

• \( 1 \leq n,q \leq 10^5 \)
• \( 1 \leq a_i, k \leq 10^9 \)
• \( 1 \leq i \leq j \leq n\)

6 3
5 1 2 3 4 5
2 4 1
4 4 4
1 6 2

2
0
4

• Query 1 (2,4,1): The range is [1,2,3] and there are 2 values greather than k=1, which are 2 and 3.
• Query 2 (4,4,4): The range is [4] and there are no greather than k=4,
• Query 3 (1,6,2): The range is [5,1,2,3,4] and there are 3 values greather than k=2, which are 5, 3, 4 and 5.