# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

# Permutation Query

By · Limits 1s, 256 MB

An array of integers $p_1,p_2,....,p_n$ is called a permutation if it contains each number from $1$ to $n$ exactly once. For example, the following arrays are permutations: $[3,1,2], [1], [1,2,3,4,5]$ and $[4,3,1,2]$. The following arrays are not permutations: $[2], [1,1], [2,3,4]$.

You are given an array of $n$ elements and $q$ queries. These queries are of two types:

• $1 \, \, l \, \, r$ means, if $A_l,A_{l+1},A_{l+2},,,,A_{r-1},A_r$ holds permutation, then print YES. Otherwise, print NO.

• $2 \text{ pos val}$ means, set $A_{pos}=val.$

## Input

The first line contains two integer $n$ and $q$$(1\leq n,q \leq 2\times10^{5})$the size of the array and the number of queries.

The second line contains $n$ integer $A_1,A_2,....,A_n$$(1\leq A_i\leq n)$.

The next $q$ lines contain two types of queries.

$Type_i \in \{1, 2\}$

$1\leq l_i\leq r_i\leq n$

$1\leq pos_i, val_i \leq n$

## Output

For every query of type $1$, print YES if $l$ to $r$ holds a permutation. Otherwise, print NO.

## Sample

InputOutput
5 4
2 1 3 4 5
1 1 5
2 4 3
1 1 5
1 1 3

YES
NO
YES


Initially, the array looks like this [2,1,3,4,5].

After the second query, the array becomes [2,1,3,3,5].

### Statistics

63% Solution Ratio

NirjhorEarliest, 1M ago

Farhan20Fastest, 0.1s

samiulsamiLightest, 4.6 MB

serotoninShortest, 1201B