KQUERY - K-query

no tags 

Đọc đề đẹp hơn ở:
https://codeforces.com/group/FLVn1Sc504/contest/274496/problem/S

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
abhishek201202: 2021-02-26 14:46:56

Are test cases are weak in this ??

mayank2120: 2021-01-28 17:03:32

Try merge sort trees that will help!! definitely

vg5823967: 2021-01-18 10:41:34

Done!

vg5823967: 2021-01-18 06:13:46

am getting TLE am using a vector for each node of segment tree.... Why?

practmperfect: 2020-11-29 17:03:28

Java merge sort tree works. I know this is basic but make sure not to use System.out.println. Use BufferedOutputStream

kanishkverma_1: 2020-11-28 20:11:38

Java merge sort Works . Just make sure ur not reinitializing the arraylist as it consumes some time .

tejameranaam: 2020-10-16 09:22:09

Merge Sort tree will give AC.

beowulf_rohan: 2020-10-02 14:20:22

Use Binary Index Tree... and use "\n" while displaying output... endl will give u TLE for a bigger q.... Othewise it takes 0.53s

mukul202: 2020-09-10 17:15:33

Seg tree gives 0.70 time
try ...:)

kumarpritam863: 2020-09-06 13:52:24

Normal Range sum Segment Tree will give AC.


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