[Ynoi2014]不归之人与望眼欲穿的人们

题目背景

【第一船队发来联络了】 【是关于第15号悬浮岛的战斗结果】 【15号悬浮岛的保卫作战...】 【失败了...】 ![](https://cdn.luogu.com.cn/upload/pic/45508.png) ![](https://cdn.luogu.com.cn/upload/pic/45509.png) ![](https://cdn.luogu.com.cn/upload/pic/45510.png) ![](https://cdn.luogu.com.cn/upload/pic/45512.png) ![](https://cdn.luogu.com.cn/upload/pic/45513.png) ![](https://cdn.luogu.com.cn/upload/pic/45514.png)

题目描述

珂朵莉给了你一个序列,支持单点修改,或者询问满足区间 or 和**大于等于**一个数的区间的最短可能长度,无解输出 $-1$。

输入输出格式

输入格式


第一行有两个整数 $n,m$。 接下来一行 $n$ 个整数,表示这个序列 $a$。 接下来 $m$ 行,形如: * $1\ i\ x$ 表示将 $a_i$ 修改为 $x$。 * $2\ k$ 表示询问最短的一个长度,满足存在一个该长度的区间,其 or 和 $\geq k$。

输出格式


对所有 $2$ 操作,输出一行,包含一个整数,表示答案,无解输出 $-1$。

输入输出样例

输入样例 #1

2 3
0 2 
2 3
1 1 1
2 3

输出样例 #1

-1
2

说明

Idea:kczno1, Solution:kczno1( $O( msqrtnlogn )$ solution ),liu_cheng_ao($O( mlog^2nlog^2a$ ) solution ) Code:kczno1( $O( msqrtnlogn )$ code ),liu_cheng_ao($O( mlog^2nlog^2a$ ) code ) ,Data:kczno1 对于 $100\%$ 的数据,$0\leq a_i,k\leq 2^{30}$,$1\leq n,m\leq 5\times 10^4$。