## KQUERY2 - K-query II

English | Vietnamese |

Given a sequence of n numbers a_{1}, a_{2}, ..., a_{n} and a number of k-queries. Besides, you are also given some modify operations.

A modify operation is a pair (i, v) which means a_{i} 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 a_{i}, a_{i+1}, ..., a_{j}.

### Input

- Line 1: n (1 ≤ n ≤ 30000).
- Line 2: n numbers a
_{1}, a_{2}, ..., a_{n}(1 ≤ a_{i}≤ 10^{4}) 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 ≤ 10
^{4}) representing a modify operation. A flag 1 follows by 3 numbers i, j and k (1 ≤ i ≤ j ≤ n, 1 ≤ k ≤ 10^{4}) representing a k-query.

### Output

- For each k-query (i, j, k), print the number of elements greater than k in the subsequence a
_{i}, a_{i+1}, ..., a_{j}in a single line.

### Example

Input5 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 2Output2 1 2

hide comments

manuelloaiza:
2021-02-20 00:21:41
I got TLE with Segment Tree with an Order Statistics Tree on each node but AC with 2D Fenwick Tree. |

Added by: | Jimmy |

Date: | 2008-10-28 |

Time limit: | 1s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |

Resource: | © VNOI |