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
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.

devo_bhai: 2020-09-05 16:46:27

merge sort tree will work and give you ac in one go hopefully if everything is correct

abhijitburman: 2020-08-19 02:27:11

AC in one go... Using merge sort segment tree..

subhram79788: 2020-07-05 05:22:26

I have tried by sorting queries which is offline method.still TLE..for confirmation u can go with this codeforces link..............https://codeforces.com/blog/entry/15890....plz check,the same method I have implemented

offamitkumar: 2020-06-15 12:21:23

After removing xor operation I submitted the same solution to this problem ( merge sort tree + online querying) and it got accepted with time 1.88.

Last edit: 2020-06-26 09:25:09
sitanshu29: 2020-06-04 07:41:17

Merge Sort Tree Gives TLE... Try using Ofline Segment Tree


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