ストーリー

悪の医者である hibit 君は、彼の野望のために最長増加部分列について勉強しています。
しばらくして hibit 君は以下の問題に出会いましたが、もう夜遅かったので明日のバーチャルコンテスト「あさかつ」に備えて寝ることにしました。
hibit 君のライバルであるあなたはその問題を hibit 君が起きる前に解こうと思いました。

問題文

$1$ 以上 $4$ 以下の整数からなる長さ $N$ の数列 $A=(A_1,A_2,\dots ,A_n)$ が与えられます。

$Q$ 個のクエリが与えられるので、順番に処理してください。クエリは次の $2$ 種類です。

• 1 l r : $A$ の連続部分列 $B=(A_l,A_{l+1},\dots ,A_r)$ について $B$ の最長広義単調増加部分列の長さを出力する。
• 2 l r x : $l\leq i \leq r$ を満たす整数 $i$ について $A_i$ を $x$ に更新する。

注釈

• 列 $X$ の部分列 : $X$ の要素をいくつか抜き出して元の順序に並べてできる列
• 列 $X$ の連続部分列 : $X$ のある連続する区間のみを取り出し順番を保ったもの
• 列 $X$ の最長広義単調増加部分列 : $X$ の広義単調増加な部分列の中で列の長さが最大であるもの

制約

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

入力

$N$
$A_1\ A_2\  \dots \ A_N$
$Q$
$query_1$
$query_2$
$\vdots$
$query_Q$

各クエリ $query_i\, (1\leq i\leq Q)$ は

$1$ $l$ $r$

または、

$2$ $l$ $r$ $x$

の形で与えられる。

出力

$1$ 種類目のクエリの数を $q$ として $q$ 行出力してください。 $i(1\leq i\leq q)$ 行目には $i$ 個目の $1$ 種類目のクエリに対する出力を出力してください。

サンプル

7
1 2 4 3 2 1 3
3
1 1 7
2 2 4 1
1 3 6

4
3

4
4 3 2 1
1
1 1 4

1

17
2 1 3 3 2 3 3 3 4 2 3 2 2 2 1 4 1
15
2 5 17 1
1 8 10
1 11 13
2 2 8 2
2 6 17 2
1 11 17
2 13 17 4
1 9 13
2 6 6 4
2 1 16 4
1 2 5
2 16 16 1
2 3 6 2
1 3 6
1 2 2

3
3
7
5
4
4
1