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)$