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
i_am_looser: 2015-06-11 18:17:07

I think with this time limit admin expect us to use BIT instead of persistent segment tree.My persistent segment tree solution gives tle with fast i/o don't know why but BIT solution gives AC ; )

Rang: 2015-06-04 19:10:36

My main logic was O((N+Q)logN) but it had a huge constant factor! Optimize(I/O, remove redundant calls, check tree etc.,) before submitting. Understood log(Q) and log(N) are very close !!!

Pagan Min: 2015-05-26 15:19:15

getting tle with persistent segment tree...can anyone share a word :(

Archit Jain: 2015-03-11 15:09:51

nice one...
finally ac after many wa's

bicsi: 2015-03-10 13:34:14

Try bit's... They're faster than segment trees! You might have to do something with the queries first... ;). Loved the problem!

californiagurl: 2015-01-17 13:33:16

i optimized I/O with segment tree but getting tle with O(n log^2 (n) ).
this problem is interesting because of the time limit :)
keep trying!

Last edit: 2015-01-18 12:00:10
Yashpal: 2015-01-08 17:58:48

Persistent segment tree with fast IO get AC !! :)

Yuriy Bondarchuck: 2015-01-02 07:56:34

I can't got AC with any of my solutions.
Persistent segment tree - TL
Segment tree of segments - TL
What is the solution????

Ishant : 2014-12-30 19:44:16

Everything comes under int !! So if you are getting TLE with (N+Q)log(N+Q) using long long could be one of the reasons!!

: 2014-12-28 08:54:31

Accept with O(n log^2(n)) :)


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