There are \(N\) points located on the X axis at positions \(A_1, A_2, \dots, A_N\) respectively. Alice performs \((N-1)\) journeys. During the \(i^{th}\) journey \((1\le i \le N - 1)\), Alice moves from \(i^{th}\) point to \((i + 1)^{th}\) point (i.e from position \(A_i\) to position \(A_{i+1}\)).

You have to answer \(Q\) queries of the following form:

• \(L_i, R_i, X_i (1 \le L_i \le R_i \le N-1)\): How many times does Alice go over point \(X_i\) during \(L_i^{th}\) to \(R_i^{th}\)journey?

Input format

• The first line of input contains \(N\) denoting the number of points on X-axis and \(Q\) denoting the number of queries.
• The second line contains \(N\) integers \(A_1, A_2, \dots, A_N\) denoting the positions of the points on the X axis.
• \(Q\) lines follow. The \(i^{th}\) of these lines contains three integers \(L_i, R_i, X_i.\)

Output format
For each query, print the answer in a separate line.

Constraints