MegaBoostFertilizer and Tree Statistics

Egon has a collection of trees and several bottles of MegaBoostFertilizer. Each bottle is characterized by two parameters: a capacity \(c_i\) and a minimal height requirement \(h_i\). When Egon uses a bottle, he applies it to the \(c_i\) smallest trees (by current height) among those trees with height at least \(h_i\). Each application increases a tree's height by exactly 1 centimeter.

In addition, Egon needs to answer several queries about his garden. Each query consists of an interval \([l, r]\), and the answer is the number of trees whose heights lie in that interval (inclusive).

Your task is to process a list of operations on the trees. There are two kinds of operations:

• Fertilizer operation: Given parameters \(c\) and \(h\) (written as 1 c h), apply the fertilizer bottle on the \(c\) smallest trees (by height) among those having height at least \(h\). If there are fewer than \(c\) such trees, apply the fertilizer to all of them.
• Query operation: Given an interval \([l, r]\) (written as 2 l r), report the number of trees whose height is between \(l\) and \(r\) (inclusive).

The operations are processed sequentially. Note that a fertilizer operation changes the heights of the trees, and these updates affect the subsequent operations.

Input/Output Format: See the sections below.

inputFormat

The input consists of multiple lines:

1. The first line contains a single integer \(n\) representing the number of trees.
2. The second line contains \(n\) integers representing the initial heights of the trees.
3. The third line contains a single integer \(q\) representing the number of operations.
4. The following \(q\) lines each describe an operation. An operation is given in one of the following two formats:
   • 1 c h: A fertilizer operation with capacity \(c\) and minimal height requirement \(h\).
   • 2 l r: A query asking for the count of trees with height in \([l, r]\) (inclusive).

outputFormat

For each query operation, output the count of trees whose height is in the given interval on a separate line.

sample

5
2 3 5 6 8
5
1 2 3
2 3 6
1 3 6
2 2 7
1 1 8

3
4