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
dhaka_1436: 2022-09-17 13:08:53

Uber OA Problem

fuadul_hasan: 2022-08-31 11:25:49

nice and easy problem.... merge sort tree + binary search. and boom ;)

olympia11111: 2022-06-10 04:39:39

offline segment tree

chainsn4tcherr: 2022-02-22 22:06:25

merge sort tree + binary search = (:

congdanh2504: 2022-02-17 01:39:27

sqrt decomposition + binary search => AC

ryuuk: 2022-02-07 08:42:10

Solved with BIT + offline queries

joynal_67: 2022-01-13 13:29:46

Use Marge Sort Tree + Binary Search

psz2007: 2022-01-13 07:15:05

Use Mo's Algorithm with time complexity O(n\sqrt{n}) and AC !!!

mahbubkuet08: 2021-11-08 19:12:32

Getting WA. Any clue?

adam____: 2021-08-25 14:16:42

used merge sort tree + bin search


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