题目内容

我们定义:

从长度为$n$的原数组中截取一段连续的下标在$[l,r]$范围内的新数组为原数组的子数组，如$[1,2]$跟$[2,3]$是数组 $[1,2,3]$的子数组，但$[1,3]$不是;

若将两个下标区间不完全相同的子数组排序后，得到完全相同的结果，则认为这两个子数组是相似的，如原数组$[5,7,6,3,6,5,7]$中，$[5,7,6]$与$[6,5,7]$是相似的。

对一个长度为$n$的数组有$2$种操作：

1.1 $x$ $y$:表示将下标为$x$的数字改为$y$;

2.2:询问该数组所有相似子数组中的最大长度。

输入描述

第一行为两个正整数$n,q(1≤n,q≤10^5)$，表示原数组的长度与操作次数，

第二行为$n$个正整数$a_i(1≤a_i≤n)$，接下去$q$行，每行对应一个操作，格式为$1$ $x$ $y$ $(1≤x,y ≤ n)$或$2$,含义如题。

输出描述

对于每个操作$2$输出询问结果。

补充说明

对于$30$%的数据，$1≤n,q≤20$; 对于$60$%的数据，$1≤n,q≤1000$; 对于$100$% 的数据，$1≤n,q≤10^5$，其它数据范围见输入 部分。

样例1

输入

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

输出

0
1
2

说明

初始数组为$[1,2,3]$，此时无相似子数组，输出$0$;

第二次操作将第一个数字修改为$2$，数组变为$[2,2,3]$，此时下标范围为$[1,1]$与$[2,2]$的两个子数组相似，因此最大相似子数组长度为$1$;

操作$4$后数组变为$[2,3,3]$，操作$5$后数组变为$[2,3,2]$，此时子数组$[2,3]$与$[3,2]$相似，最大长度为$2$。