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
Abhishek Jaisingh:
20161217 23:28:06
segtree + offline = AC!! <3 

Ravi kumar:
20161025 21:17:45
persistence segment tree with fast io accepted :) 

akchoubey:
20161007 16:23:53
I applied segment tree at first and got TLE


V Manikantan:
20161005 15:43:01
Persistent segment trees works comfortably 

blackjack123:
20161003 22:42:02
my 100 th 

RISHAV KUMAR:
20161001 00:31:40
Has anyone done it in java using BIT..? I'm getting TLE, while the same code in c++ is getting passed. such a pain.. Last edit: 20161001 00:31:57 

divide_by_1:
20160829 06:32:59
Did some one got AC with sqrt decomposition ? 

buttman:
20160718 16:19:16
time limit should be increased a bit. 

askerov:
20160707 17:19:18
I wrote Segment Tree, but it doesn't work. I have got TLE. What is Time limit: 0.184s? only build gets 0.2s 

proficient:
20160525 16:49:56
Anyone got AC with O( Q log^2 (N) ) ? I get TLE even with fast IO, typedef and inline functions. 
Added by:  Duc 
Date:  20081026 
Time limit:  0.184s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JS NODEJS PERL 6 VB.net 
Resource:  © VNOI 