KQUERY - K-query

no tags 

Given a sequence of n numbers a1, a2, ..., an and a number of k- queries. A k-query is a triple (i, j, k) (1 ≤ i ≤ j ≤ n). For each k-query (i, j, k), you have to return the number of elements greater than k in the subsequence ai, ai+1, ..., aj.

Input

  • Line 1: n (1 ≤ n ≤ 30000).
  • Line 2: n numbers a1, a2, ..., an (1 ≤ ai ≤ 109).
  • 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 k-query (1 ≤ i ≤ j ≤ n, 1 ≤ k ≤ 109).

Output

  • For each k-query (i, j, k), print the number of elements greater than k in the subsequence ai, ai+1, ..., aj 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: 2014-12-27 22:49:15

really good problem!! worth solving :)
Be careful with the I/O. Large input/output data...

Last edit: 2014-12-27 23:15:16
Jacob Plachta: 2014-11-19 06:31:48

Moved to Classical, as suggested - I do think it belongs there, even if there exist somewhat similar problems.

Pratik kumar: 2014-02-13 22:23:36

Should be moved to classical....nice question

Jordan Alexander: 2013-12-20 20:34:48

The author really needs to make the time limits more lenient. A non-optimally 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: 2014-12-27 23:16:51

Added by:Duc
Date:2008-10-26
Time limit:0.184s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:© VNOI