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
swapnil_007:
20170812 00:03:03
Merge sort tree(iterative)+fast i/o....got tle....


jisan047:
20170722 14:04:14
i use MST but getting WA :( 

sharanx:
20170720 20:57:20
Offline +segment tree=AC !!! :) 

avsievich:
20170720 15:27:11
fenwick + scanline  ac 

starbot:
20170629 20:41:24
BIT.,..,,.,..,.,is a gud ds 

sandeepg97:
20170629 04:57:57
Finally AC :)..MST :D 

prakhar10_10:
20170628 06:46:19
Woah! now my online persistent segment tree solution is accepted. 

sandeepg97:
20170627 12:42:33
Yeah, persistent segment tree also TLE. Can someone who has solved this help us out here? 

prakhar10_10:
20170627 01:56:06
Done with sorting and segment tree, but TLE with persistent segment tree. 

prakhar10_10:
20170627 01:50:56
Persistent segment tree is giving TLE 
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 