题目描述

You are playing a board game with squares numbered from $0$ to $10^9$ (inclusive) and $N$ tokens numbered from $1$ to $N$. Each token is located in one of the squares, and multiple tokens might be located in the same square. Initially, token $i$ is located in square $T_i$. The distance of the two tokens is the difference between the square number where the first token is located and the square number where the second token is located.

For a set of tokens $S$, we would like to check whether the tokens are well-separated as follows:

• Let $A$ be the list of tokens in $S$ sorted by increasing order of square number where the token is located. If several tokens are located in the same square, then these tokens are sorted by increasing order of token number.
• If there are less than three tokens in $A$, then the tokens are well-separated.
• Otherwise, the tokens are well-separated if and only if the distance between two neighbouring tokens in $A$ is the same. Two tokens are neighbouring if their indices in $A$ differ by one.

You would like to perform $Q$ operations of either one of these types:

1. Move token $X$ to square $Y$.
2. Report whether the set of tokens numbered from $L$ to $R$ (inclusive) are well-separated.

输入格式

Input begins with a line containing two integers: $N\ Q$ ($2 \leq N \leq 100\,000$; $1 \leq Q \leq 100\,000$) representing the number of tokens and the number of operations, respectively. The next line contains $N$ integers: $T_i$ ($0 \leq T_i \leq 10^9$) representing the initial square location of the tokens. The next $Q$ lines each contains one of the following input format representing the operation you should perform.

• $1\ X\ Y$ ($1 \leq X \leq N$; $0 \leq Y \leq 10^9$)
  Move token $X$ to square $Y$.
• $2\ L\ R$ ($1 \leq L < R \leq N$)
  Output whether the set of tokens numbered from $L$ to $R$ (inclusive) are well-separated.

There will be at least one operation of the second type.

输出格式

For each operation of the second type in the same order as input, output in a line a string "YES" (without quotes) or "NO" (without quotes) whether the set of tokens numbered from $L$ to $R$ (inclusive) are well-separated.

5 7
1 1 1 10 1
2 1 3
2 1 5
1 5 4
1 3 7
2 2 4
2 2 5
2 4 5

YES
NO
NO
YES
YES

提示

Explanation for the sample input/output #1

• Initially, the tokens are located in the square numbered $[1, 1, 1, 10, 1]$.
• For the first operation, the distance between two neighbouring tokens in $A = [1, 2, 3]$ is $0$ and $0$. Therefore, the tokens are well-separated.
• For the second operation, the distance between two neighbouring tokens in $A = [1, 2, 3, 5, 4]$ is $0, 0, 0$, and $9$. Therefore, the tokens are not well-separated.
• After the third and fourth operations, the tokens are located in the square numbered $[1, 1, 7, 10, 4]$.
• For the fifth operation, the distance between two neighbouring tokens in $A = [2, 3, 4]$ is $6$ and $3$. Therefore, the tokens are not well-separated.
• For the sixth operation, the distance between two neighbouring tokens in $A = [2, 5, 3, 4]$ is $3, 3$, and $3$. Therefore, the tokens are well-separated.
• For the seventh operation, $A = [5, 4]$ has less than three tokens. By definition, the tokens are well-separated.