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
abhi2402:
20190617 08:49:04
C++ PBDS + Offline querying gets it in 0.27s. 

ab_biswas09:
20190318 23:49:20
After So Many TLEs finally AC


vivek_rathi:
20190317 08:07:30
Use scanf and printf otherwise TLE 

davidgalehouse:
20190217 02:12:03
Easier than DQUERY in my opinion. Less creativity required in applying the BIT. 

abhinav_jain02:
20190201 10:07:19
Try to use BIT instead of segment trees. It works faster and has a smaller code. 

a_98:
20181123 14:03:30
BIT does it in 0.17 without fast IO. 

yaseenmollik:
20181115 21:35:34
First problem using Offline queries with segment tree :D 

phoemur:
20181023 02:08:31
BIT + Offline Query = 0.20s


alexandro5432:
20181012 16:09:24
silxikys time limit is 0.184s for each test. Your solution worked in 0.4s for all the tests summed up 

silxikys:
20180827 05:31:43
Can be solved using sqrtdecomposition of array and coordinate compression, my sol is 0.4 seconds. Not sure what the 0.184s time limit means. 
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 