KQUERY2 - K-query II

no tags 

Given a sequence of n numbers a1, a2, ..., an and a number of k-queries. Besides, you are also given some modify operations.

A modify operation is a pair (i, v) which means ai should be set to be v.

A k-query is a triple (i, j, k). 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 ≤ 104) representing the initial sequence.
  • Line 3: q (1 ≤ q ≤ 200000), the number of operations.
  • In the next q lines, the first number of each line contains a flag value which is either 0 or 1. A flag 0 follows by 2 numbers i and v (1 ≤ i ≤ n, 1 ≤ v ≤ 104) representing a modify operation. A flag 1 follows by 3 numbers i, j and k (1 ≤ i ≤ j ≤ n, 1 ≤ k ≤ 104) representing a k-query.

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
6
1 2 4 1
0 4 10
1 4 4 4
0 3 1
0 1 2
1 1 5 2 

Output
2
1
2

hide comments
sharanx: 2017-12-07 08:57:02

decomposition+BIT=AC in one go :)

Puneet: 2017-06-24 06:38:17

Is there any way to solve this and KQUERY using Segment tree without offline queries.
And how will it be solved using offline queries with segment tree ?????

Min_25: 2016-08-13 07:42:40

Should be moved to classical.

kliu31415: 2016-01-22 06:00:30

Is there any way to request this problem to be moved? This is definitely at least a medium difficulty problem (I think this requires knowledge of a 2D range tree).

Scape: 2015-11-03 17:07:27

This should not be in tutorial.

[deleted]: 2015-02-12 11:14:08

Why is this problem in tutorial ?


Added by:Duc
Date:2008-10-28
Time limit:0.850s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:© VNOI