## CPAIR - Counting pairs

no tags

You're given a sequence A of N non-negative integers. Answer Q queries, where each query consists of three integers: v, a, b. The answer is number of pairs of integers i and j that satisfy these conditions:

1 <= i <= j <= N

a <= j-i+1 <= b

A[k] >= v for every integer k between i and j, inclusive

### Constraints

1 <= N <= 100 000

1 <= Q <= 100 000

0 <= A[k] <= 1000, for every integer k between 1 and N, inclusive

0 <= v <= 1000

1 <= a <= 100 000

1 <= b <= 100 000

### Input

The first line of input contains two integers, N and Q. The second line contains the sequence A, consisting of N integers. Each of the next Q lines contains three numbers, v, a and b, defining a query.

### Output

In the i-th line output only one integer denoting the answer to the i-th query.

### Example

```Input:
5 3
5 3 2 7 4
3 2 3
2 2 5
4 1 1

Output:
2
10
3
``` anshul_srivas: 2016-09-16 15:12:13 Last edit: 2016-09-16 15:12:35 Rang: 2015-06-15 08:15:23 O(N+Q)lgN with Fenwick Trees (+Bsearch) Passes :) O(N+Q)LogN with Fenwicktrees and DSU should also pass :) . O(N*DistinctVs+Qlogn) will exceed time limit! FOX: 2015-05-01 23:10:25 O(N) solution and TLE? Last edit: 2015-05-02 00:07:50 Voyage: 2011-09-30 07:35:10 How come O(N log N + Q log N) got TLE?