KQUERY  Kquery
English  Vietnamese 
Given a sequence of n numbers a_{1}, a_{2}, ..., a_{n} and a number of k queries. A kquery is a triple (i, j, k) (1 ≤ i ≤ j ≤ n). For each kquery (i, j, k), you have to return the number of elements greater than k in the subsequence a_{i}, a_{i+1}, ..., a_{j}.
Input
 Line 1: n (1 ≤ n ≤ 30000).
 Line 2: n numbers a_{1}, a_{2}, ..., a_{n} (1 ≤ a_{i} ≤ 10^{9}).
 Line 3: q (1 ≤ q ≤ 200000), the number of k queries.
 In the next q lines, each line contains 3 numbers i, j, k representing a kquery (1 ≤ i ≤ j ≤ n, 1 ≤ k ≤ 10^{9}).
Output
 For each kquery (i, j, k), print the number of elements greater than k in the subsequence a_{i}, a_{i+1}, ..., a_{j} in a single line.
Example
Input 5 5 1 2 3 4 3 2 4 1 4 4 4 1 5 2 Output 2 0 3
hide comments
siva2697:
20180217 08:28:40
input:(scanf,printf) + Approach (Segment_Trees) + Solution(Discussed in Codeforces Algorithm Gym by DarthPrince) :AC


amitboss:
20180203 06:11:32
can it be solved using segment tree+online ? 

sadman2901:
20180115 04:52:09
BIT + Sorting each segment + Sorting query + Binary search + Optimization + Faster I/O, it worked in 0.35 :) 

rishabhm123:
20180101 15:27:36
I am getting TLE with segment trees too..any suggestions


optimus_v2:
20180101 10:40:45
Classical offline segment tree problem . First i tried classical + online got TLE , then classical + offline got AC Last edit: 20180101 10:41:24 

dragon_162:
20171230 12:02:48


karthik1997:
20171229 16:54:08
Segment tree 0.15 and BIT 0.10 with fast i/o . Cant go below it :( . How could people get below 0.1s :O 

lostground97:
20171221 10:27:58
Can this be done using Normal Segment Tree?


shubhamkr2020:
20171218 12:45:06
accepted using printf but tle using cout.


ashutosh_gajre:
20171214 10:06:53
I guess sqrt decomposition does not work at all. 
Added by:  Duc 
Date:  20081026 
Time limit:  0.184s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  © VNOI 