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

hide comments
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?


Added by:Stjepan Glavina
Date:2009-12-05
Time limit:0.514s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 NODEJS OBJC PERL6 SQLITE VB.NET
Resource:own problem