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
[Rampage] Blue.Mary: 2016-01-21 04:30:15

OK. The test data seems not satisfy the conditions mentioned in problem description. I assume the following:
if i<1: i = 1
if j>n: j = n
if i>j: res->0

spoj2121: 2015-12-27 18:45:27

merge sort tree..with fast I/O = 3rd fastest solution ^_^

khoonicoder: 2015-09-02 04:38:34

Merge Sort Tree gives AC in first time while Persistent Segment Tree giving the Segmentation Fault
In the sample input fourth query becomes (0,0) where constraint of 1<=i,j<=n gets violated while doing such on Merge Sort Tree it automatically gets handle, but on the Persistent Segment Tree it is accessing the wrong memory bounds
This question made me learn several things, but please correct the input/output
Regards,
KhooniCoder

Pulkit Singhal: 2015-09-01 11:22:33

Can someone please explain sample test case 4th and 5th query

mehmetin: 2015-05-08 17:48:26

Sample test cases are correct. There was a broken input issue, that was the reason of TLE's.

Last edit: 2015-05-14 17:28:54
kuldeep yadav: 2015-05-07 06:37:04

Accepted in 1 try

kuldeep yadav: 2015-05-07 05:58:21

Test case is wrong

Last edit: 2015-05-07 06:36:27
js2072: 2015-04-30 18:42:10

isn't 0 0 0 1 1 the right answer for the test case?

Rajat De: 2015-04-24 16:07:07

why is O(sqrt(n) ) per query failing ? it should pass

adamant: 2015-04-21 12:40:20

Are you kidding?! simply return 0 gets AC :|


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