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
karan_yadav:
20180802 12:12:48
A really Ingenious solution is provided by Raziman T.V., A must read I'd say.


wjli:
20180728 04:40:00
online query can be answered thru persistent segment tree. 

kissu_pari_na:
20180710 03:34:11
At first try using Merge Sort Tree, got TLE, then solved using segment tree + offline query Last edit: 20180710 03:34:37 

horizon121:
20180526 21:17:55
Interesting!!Learned a lot . My first using SegTree+Offline query . Good one 

ayush926:
20180524 20:30:30
BIT+Offline+Fast I/O > 0.25s 

devarshi09:
20180523 12:39:37
Time limit is too strict for merge sort tree!


jwalinarora:
20180326 02:42:55
How to handle sigbus error?


dhruvsomani:
20180322 19:38:25
If you are using the offline segtree/BIT method, then scanf/printf is necessary. 

bradyawn:
20180311 19:50:59
https://hastebin.com/ewobuzater.cpp


kaneki13:
20180311 16:30:00
I have tried to do it using online processing. I built a segment tree in which each node stores the sorted vector with elements from l to r and performed queries online and I am getting tle. any suggestion to get it accepted or will it not work altogether? 
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 