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
meettaraviya:
20170324 06:04:19
AC in 1st go :') 

razor123:
20170303 14:00:00
Those getting TLE with seg tree...build the tree iteratively. Last edit: 20170304 07:33:15 

avisheksanvas:
20170226 08:02:32
Don't use cin, cout. Gives TLE! 

ap_whitehat:
20170212 17:34:30
Weird !


fnf:
20170211 18:34:57
Simple sorting + BIT =AC 

shubham2305:
20170201 10:06:08
word of advice for lazy coders like me


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 
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 