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
devarshi09: 2018-05-23 12:39:37

Time limit is too strict for merge sort tree!

jwalinarora: 2018-03-26 02:42:55

How to handle sigbus error?

dhruvsomani: 2018-03-22 19:38:25

If you are using the offline segtree/BIT method, then scanf/printf is necessary.

bradyawn: 2018-03-11 19:50:59

https://hastebin.com/ewobuzater.cpp

If I change que[200001] to que[200000] it will RTE, but right now it ACs.

Is there something wrong with the tests?

kaneki13: 2018-03-11 16:30:00

I have tried to do it using online processing. I built a segment tree in which each node stores the sorted vector with elements from l to r and performed queries online and I am getting tle. any suggestion to get it accepted or will it not work altogether?

siva2697: 2018-02-17 08:28:40

input:(scanf,printf) + Approach (Segment_Trees) + Solution(Discussed in Codeforces Algorithm Gym by DarthPrince) :AC
be Cautious with input output
Even std::ios::sync_with_stdio(false) with cin,cout gives TLE :(

Last edit: 2018-02-17 08:31:48
amitboss: 2018-02-03 06:11:32

can it be solved using segment tree+online ?

sadman2901: 2018-01-15 04:52:09

BIT + Sorting each segment + Sorting query + Binary search + Optimization + Faster I/O, it worked in 0.35 :)

rishabhm123: 2018-01-01 15:27:36

I am getting TLE with segment trees too..any suggestions
I am storing a sorted vector in each node and using upper_bound to find result..

optimus_v2: 2018-01-01 10:40:45

Classical offline segment tree problem . First i tried classical + online got TLE , then classical + offline got AC

Last edit: 2018-01-01 10:41:24

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