KQUERYO - K-Query Online

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 a, b, c representing a k-query. You should do the following:
    • i = a xor last_ans
    • j = b xor last_ans
    • k = c xor last_ans
    After that 1 ≤ i ≤ j ≤ n, 1 ≤ k ≤ 109 holds.
    Where last_ans = the answer to the last query (for the first query it's 0).

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:
6
8 9 3 5 1 9
5
2 3 5
3 3 7
0 0 11
0 0 2
3 7 4

Output:
1
1
0
0
2

[Edited by EB]

There are invalid queries. Assume the following:
  • if i < 1: i = 1
  • if j > n: j = n
  • if i > j: ans = 0

hide comments
louhc: 2019-01-19 16:08:41

forget continuing...... silly me

a_98: 2019-01-01 12:16:12

Persistent Segment Tree + Binary Search does it !

Erick: 2018-08-28 07:14:00

Finally AC!
Tip: Don't use the third if putted by EB (i > j: ans = 0) it causes WA!!

tisparta: 2018-08-09 05:43:20

Also solvable with Wavelet tree e.e

amulyagaur: 2018-03-14 07:12:34

same concept can be applied here as well:
https://www.codechef.com/problems/PRMQ

madhur4127: 2018-02-26 14:50:18

O(sqrt(N)*log(N)) gives AC in 0.12s, how to reduce time other than using merge sort tree?

ayushgupta1997: 2018-02-22 14:05:42

The test cases are weak sqrt decomp also passes...even i didn't use long long for a[] still passed :(

ramini1996: 2018-02-05 11:05:10

AC in ONE GO !!!

shiv2111: 2018-01-12 10:32:34

same version KQUERY has very strict TL, merge sort tree is not going to work there.

sherlock726: 2017-10-16 20:56:51

ac on first go
simple segment tree + vector for each node


Added by:amirmd76
Date:2015-04-17
Time limit:0.200s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All