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

devo_bhai:
20200905 16:46:27
merge sort tree will work and give you ac in one go hopefully if everything is correct


abhijitburman:
20200819 02:27:11
AC in one go... Using merge sort segment tree.. 

subhram79788:
20200705 05:22:26
I have tried by sorting queries which is offline method.still TLE..for confirmation u can go with this codeforces link..............https://codeforces.com/blog/entry/15890....plz check,the same method I have implemented


offamitkumar:
20200615 12:21:23
After removing xor operation I submitted the same solution to this problem ( merge sort tree + online querying) and it got accepted with time 1.88.


sitanshu29:
20200604 07:41:17
Merge Sort Tree Gives TLE... Try using Ofline Segment Tree 
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 