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
i_am_looser:
20150611 18:17:07
I think with this time limit admin expect us to use BIT instead of persistent segment tree.My persistent segment tree solution gives tle with fast i/o don't know why but BIT solution gives AC ; ) 

Rang:
20150604 19:10:36
My main logic was O((N+Q)logN) but it had a huge constant factor! Optimize(I/O, remove redundant calls, check tree etc.,) before submitting. Understood log(Q) and log(N) are very close !!! 

Pagan Min:
20150526 15:19:15
getting tle with persistent segment tree...can anyone share a word :( 

Archit Jain:
20150311 15:09:51
nice one...


bicsi:
20150310 13:34:14
Try bit's... They're faster than segment trees! You might have to do something with the queries first... ;). Loved the problem! 

californiagurl:
20150117 13:33:16
i optimized I/O with segment tree but getting tle with O(n log^2 (n) ).


Yashpal:
20150108 17:58:48
Persistent segment tree with fast IO get AC !! :) 

Yuriy Bondarchuck:
20150102 07:56:34
I can't got AC with any of my solutions.


Ishant :
20141230 19:44:16
Everything comes under int !! So if you are getting TLE with (N+Q)log(N+Q) using long long could be one of the reasons!! 

:
20141228 08:54:31
Accept with O(n log^2(n)) :) 
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 