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
meettaraviya: 2017-03-24 06:04:19

AC in 1st go :')

razor123: 2017-03-03 14:00:00

Those getting TLE with seg tree...build the tree iteratively.

Last edit: 2017-03-04 07:33:15
avisheksanvas: 2017-02-26 08:02:32

Don't use cin, cout. Gives TLE!

ap_whitehat: 2017-02-12 17:34:30

Weird !
time limit says .184 s
but my solution was accepted with running time .44 s


=(Francky)=> Nothing weird. time limit is for one input file. You got AC, and were given a TOTAL running time.

Last edit: 2017-02-12 17:56:07
fnf: 2017-02-11 18:34:57

Simple sorting + BIT =AC

shubham2305: 2017-02-01 10:06:08

word of advice for lazy coders like me
never ever use cin cout for segment trees
costed me many tles

Abhishek Jaisingh: 2016-12-17 23:28:06

segtree + offline = AC!! <3

Ravi kumar: 2016-10-25 21:17:45

persistence segment tree with fast io accepted :)

akchoubey: 2016-10-07 16:23:53

I applied segment tree at first and got TLE
then applied fast I/O and I now get segmentation fault. What might be the problem??
Please help

V Manikantan: 2016-10-05 15:43:01

Persistent segment trees works comfortably


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