D. Dynamic Collection
time limit per test
3.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a collection of elements, each of which is a positive integer. Duplicate elements are allowed in this collection. There are two types of operations that you can perform on this collection. Operation 1 is for updating the collection, and Operation 2 is for querying the collection. The format for these operations are as follows:

  • Operation 1: "1 k"
  • Operation 2: "2 a b"

For Operation 1, $$$k$$$ is an integer upon which the following rules will be applied in order:

  1. If the element $$$k$$$ is already in the collection, the collection remains the same.
  2. If the element $$$k$$$ is greater than any of the elements in the collection, it is added to the collection.
  3. The first occurrence of the smallest element greater than $$$k$$$ is replaced by $$$k$$$.

For Operation 2, $$$a$$$ and $$$b$$$ are two integers that define a range. The purpose of this operation is to query how many elements in the collection fall within this range (inclusive).

Input

The input consists of a single test case.

The first line contains two positive integers, n and q $$$(1 \leq n \leq 10^6; 1 \leq q \leq 10^6)$$$, which represent the number of elements in the collection and the total number of operations to be performed on the collection, respectively.

The second line contains exactly n space-separated integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_N$$$ $$$(1 \leq a_i \leq 10^9)$$$.

The next q lines each represent an operation. Each operation is either of type 1 or type 2, and follows the format: "1 k" or "2 a b", $$$(1 \leq a, b, k \leq 10^9; a \leq b)$$$

Output

For each Operation 2 (query operation) in the input, print a single line containing a positive integer, which represents the total number of elements in the collection that fall within the range [a, b].

Example
Input
10 11
7 1 7 1 3 9 7 9 10 4
2 2 8
1 8
2 2 8
2 1 20
1 20
2 1 20
2 7 12
1 5
2 7 12
1 12
2 7 12
Output
5
6
10
11
6
5
6
Note

Let's consider the first four operations in the example:

The initial collection is the following:

$$$C = \{7, ~1, ~7, ~1, ~3, ~9, ~7, ~9, ~10, ~4\}$$$

After the operation "2 2 8" the output is 5.

After the operation "1 8" the collection becomes:

$$$C = \{7, ~1, ~7, ~1, ~3, ~8, ~7, ~9, ~10, ~4\}$$$

Now, after operation "2 2 8" the output is 6.

After the operation "1 20" the collection becomes:

$$$C = \{7, ~1, ~7, ~1, ~3, ~8, ~7, ~9, ~10, ~4, ~20\}$$$