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
Vaibhav Gosain:
20141227 22:49:15
really good problem!! worth solving :)


Jacob Plachta:
20141119 06:31:48
Moved to Classical, as suggested  I do think it belongs there, even if there exist somewhat similar problems. 

Pratik kumar:
20140213 22:23:36
Should be moved to classical....nice question


Jordan Alexander:
20131220 20:34:48
The author really needs to make the time limits more lenient. A nonoptimally coded solution that runs in appropriate complexity doesn't pass. This is a tutorial data structures program, not an optimization problem. If someone approaches this problem from the wrong angle they could think their entire data structure is wrong, instead of thinking the problem is with the efficiency of some trivial part of their solution... Last edit: 20141227 23:16:51 
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 