問題文

長さ $N$ の整数列 $A = (A_1,A_2,...,A_N)$ が与えられます。以下の $Q$ 個のクエリに答えてください。

クエリは次の $2$ 種類のいずれかです。

1種類目のクエリは、1 i x の形式で与えられます。これは、$A_i$ を $x$ に変更することを表します。

2種類目のクエリは、2 l r の形式で与えられます。これは、$B = (A_{l},A_{l + 1},...,A_{r})$ に対して、以下の問題の答えを求めて出力することを表します。

$B$ を $1$ 個以上の非空な連続部分列に分割し、分割した列全てについて中央値を計算した後、さらにその中央値たちを並べて一つの列とみなし、その中央値を計算します。
分割する方法は全部で $2^{r - l}$ 通りありますが、適切に分割したときにこの値は最大でいくつになるでしょうか？
ここで、長さ $L$ の整数列 $X$ の中央値とは、 $X$ を昇順ソートした列を $X'$ としたときに、 $X'$ の $\lfloor \frac{L + 1}{2}\rfloor$ 番目の値のことをいいます。ただし、$\lfloor x\rfloor$ は $x$ 以下の最大の整数です。

制約

• $1 \leq N,Q \leq 2 \times 10^5$
• $1 \leq A_i \leq 10^9$
• 1種類目のクエリについて、$1 \leq i \leq N$
• 1種類目のクエリについて、$1 \leq x \leq 10^9$
• 2種類目のクエリについて、$1 \leq l \leq r \leq N$
• 入力はすべて整数

$N$ $Q$
$A_1$ $A_2$ $\ldots$ $A_N$
$\text{query}_1$
$\text{query}_2$
$\vdots$
$\text{query}_Q$

$1$ $i$ $x$

$2$ $l$ $r$

5 6
5 2 3 6 1
2 1 3
1 3 9
2 3 4
2 1 5
1 2 1
2 1 5

3
6
5
5