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