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

supriyanta:
20180809 21:56:20
BIT + offline query.


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