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
frozen7: 2017-10-17 10:46:46

BIT + Sorting in descending + Offline + Fast I/O + scanf,printf : AC.. :-)

Last edit: 2017-10-17 10:53:26
a_kk: 2017-10-03 17:07:16

using merge sort tree, how to avoid TLE :(

Last edit: 2017-10-03 17:08:34
rishi_07: 2017-09-28 10:41:55

Learnt something new! Great problem..

stommydx: 2017-09-10 19:31:20

BIT + fast IO still gives TLE :C

siddharth_0196: 2017-09-02 11:44:40

BIT + offline!

swapnil_007: 2017-08-12 00:03:03

Merge sort tree(iterative)+fast i/o....got tle....

jisan047: 2017-07-22 14:04:14

i use MST but getting WA :(

sharanx: 2017-07-20 20:57:20

Offline +segment tree=AC !!! :)

avsievich: 2017-07-20 15:27:11

fenwick + scanline - ac

starbot: 2017-06-29 20:41:24

BIT.,..,,.,..,.,is a gud ds


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