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

\(2 \leq N, Q \leq 2\cdot 10^5\\ 1\le A_i, X_i \le 10^9\\ A_i \neq A_{i+1}\\ 1 \le L _i \le R_i\le N - 1 \\X_i \neq A_j (1 \le i \le Q, 1\le j \le N)\)