题目描述

给定一个长度为 $n$ 的整数序列 $a_1, a_2, \ldots, a_n$，以及 $m$ 次操作，操作有两类：

• 1 x v：把 $a_x$ 修改为 $v$。
• 2 l r：询问区间 $[l, r]$ 内，最长的「连续相同数字」的长度。

例如序列 1 1 2 2 1 1，整个区间的最长连续相同段长度为 2。

输入格式

第一行两个整数 $n, m$（$1 \le n, m \le 10^5$）。

第二行 $n$ 个整数 $a_i$（$1 \le a_i \le 10^9$）。

接下来 $m$ 行，每行三个整数，格式如题目描述。保证 $1 \le l \le r \le n$，$1 \le v \le 10^9$。

输出格式

对每个 2 类操作，输出一行一个整数表示答案。

样例 #1

6 3
1 1 2 2 1 1
2 1 6
1 3 1
2 1 6

2
3

第一次询问，最长连续段是开头的 1 1 或中间的 2 2，长度 2；把 $a_3$ 改成 1 后，前三个数变成 1 1 1，长度 3。

提示

对于 30% 的数据，$n, m \le 1000$；对于 100% 的数据，$n, m \le 10^5$。