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
a_98: 2018-11-23 14:03:30

BIT does it in 0.17 without fast IO.

yaseenmollik: 2018-11-15 21:35:34

First problem using Offline queries with segment tree :D

phoemur: 2018-10-23 02:08:31

BIT + Offline Query = 0.20s
SegTree + Offline Query = 0.31s
MergeSort Tree + Online Query = TLE

alexandro5432: 2018-10-12 16:09:24

silxikys time limit is 0.184s for each test. Your solution worked in 0.4s for all the tests summed up

silxikys: 2018-08-27 05:31:43

Can be solved using sqrt-decomposition of array and coordinate compression, my sol is 0.4 seconds. Not sure what the 0.184s time limit means.

supriyanta: 2018-08-09 21:56:20

BIT + offline query.
no need to use fast io etc etc.....

karan_yadav: 2018-08-02 12:12:48

A really Ingenious solution is provided by Raziman T.V., A must read I'd say.
Follow the link - https://www.quora.com/How-will-you-solve-the-K-Query-using-segment-trees

wjli: 2018-07-28 04:40:00

online query can be answered thru persistent segment tree.

kissu_pari_na: 2018-07-10 03:34:11

At first try using Merge Sort Tree, got TLE, then solved using segment tree + offline query

Last edit: 2018-07-10 03:34:37
horizon121: 2018-05-26 21:17:55

Interesting!!Learned a lot . My first using SegTree+Offline query . Good one


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