CPAIR  Counting pairs
You're given a sequence A of N nonnegative 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 <= ji+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 ith line output only one integer denoting the answer to the ith 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:
20160916 15:12:13
Last edit: 20160916 15:12:35 

Rang:
20150615 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:
20150501 23:10:25
O(N) solution and TLE? Last edit: 20150502 00:07:50 

Voyage:
20110930 07:35:10
How come O(N log N + Q log N) got TLE? 
Added by:  Stjepan Glavina 
Date:  20091205 
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 