题目描述

在混沌初生的年代，王国的长老们正在研究一条古老的法则：

“只有当力量之间保持和谐，世界才能不被撕裂。”

给定长度为 $n$ 的数能序列 $a$，称区间 $[l,r]$ 为「好区间」，当且仅当不存在 $l\le i<j\le r$ 使得：

$\dfrac{a_i\times a_j}{a_i+a_j}>\sum\limits_{\substack{k=l\\k\ne i,k\ne j}}^r a_k$。

即：任意两种能量的“协同效应”不会超过其他能量的总和。

你需要处理 $q$ 次操作 $(op,x,y)$：

• 若 $op=1$：先知改变了能量流，将 $a_x$ 赋值为 $y$。
• 若 $op=2$：长老询问在区间 $[x,y]$ 中的最长好区间长度。

输入格式

第一行包含两个整数 $n$ 和 $q$，依次表示序列长度和操作次数。

第二行包含 $n$ 个整数，其中第 $i$ 个整数表示 $a_i$。

接下来 $q$ 行，每行包含三个整数 $op,x,y$，表示一次操作。

输出格式

对每次询问输出一行一个整数，表示这次询问的答案。

输入输出样例 #1

输入 #1

5 5
1 3 8 4 60
2 2 5
2 1 3
1 5 10
2 1 5
2 3 5

输出 #1

3
1
5
1

输入输出样例 #2

输入 #2

12 10
3 11 7 50 6 6 68 154 12 10 11 13
2 1 12
2 2 2
1 5 8
2 7 11
2 5 12
2 1 11
1 7 6
2 6 10
2 4 9
2 1 10

输出 #2

12
1
4
8
11
5
5
10

说明 / 提示

数据范围

对于所有数据，保证：

• $1\le n,q\le 2\times 10^5$；
• $1\le a_i\le 10^{12}$；
• $op=1$ 时，$1\le x\le n$，$1\le y\le 10^{12}$；
• $op=2$ 时，$1\le x\le y\le n$。

样例解释 #1

对于第一个查询，最长好区间是 $[2,4]$。

对于第二个查询，任意长度为 $1$ 的区间都是最长好区间。

然后将 $a_5$ 修改为 $10$，原序列变成 $1,3,8,4,10$。

对于第三个查询，最长好区间是 $[1,5]$。

对于第四个查询，任意长度为 $1$ 的区间都是最长好区间。