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

siva2697:
20180217 08:28:40
input:(scanf,printf) + Approach (Segment_Trees) + Solution(Discussed in Codeforces Algorithm Gym by DarthPrince) :AC


amitboss:
20180203 06:11:32
can it be solved using segment tree+online ? 

sadman2901:
20180115 04:52:09
BIT + Sorting each segment + Sorting query + Binary search + Optimization + Faster I/O, it worked in 0.35 :) 

rishabhm123:
20180101 15:27:36
I am getting TLE with segment trees too..any suggestions


optimus_v2:
20180101 10:40:45
Classical offline segment tree problem . First i tried classical + online got TLE , then classical + offline got AC Last edit: 20180101 10:41:24 
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 