You are given array $A$ of $n$ integers.
There are $q$ queries, each of the form $(l, r, k)$, count the number of numbers larger than $k$ in the subarray $A_l,A_{l + 1},...,A_r$.
### Input
- The first line contains 2 integers $n, q$.
- The second line contains $n$ integers $A_i$.
- The next $q$ lines, each line contains 3 integers $l, r,k$, a query.
### Output
- Print $q$ integers, the answers to $q$ queries.
### Constraints
- $1 \le n, q\le 10^5$.
- $1 \le A_i, k \le 10^9$.
### Example
Input:
```
5 3
1 2 2 3 2
1 3 1
1 5 2
3 4 5
```
Output:
```
2
1
0
```
