KQUERY  Kquery
https://codeforces.com/group/FLVn1Sc504/contest/274496/problem/S
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
abhishek201202:
20210226 14:46:56
Are test cases are weak in this ?? 

mayank2120:
20210128 17:03:32
Try merge sort trees that will help!! definitely 

vg5823967:
20210118 10:41:34
Done!


vg5823967:
20210118 06:13:46
am getting TLE am using a vector for each node of segment tree.... Why? 

practmperfect:
20201129 17:03:28
Java merge sort tree works. I know this is basic but make sure not to use System.out.println. Use BufferedOutputStream 

kanishkverma_1:
20201128 20:11:38
Java merge sort Works . Just make sure ur not reinitializing the arraylist as it consumes some time . 

tejameranaam:
20201016 09:22:09
Merge Sort tree will give AC. 

beowulf_rohan:
20201002 14:20:22
Use Binary Index Tree... and use "\n" while displaying output... endl will give u TLE for a bigger q.... Othewise it takes 0.53s 

mukul202:
20200910 17:15:33
Seg tree gives 0.70 time


kumarpritam863:
20200906 13:52:24
Normal Range sum Segment Tree will give AC. 
Added by:  Jimmy 
Date:  20081026 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  Gomoku 