down

题目描述

有一排 $n$ 个柱子，第 $i$ 个柱子的高度为 $a_i$。魔法师小 D 会从一个柱子出发，向右跳跃三次，每次都要跳到一根严格更高的柱子，方可进行施法。即小 D 会选择 $i_1<i_2<i_3<i_4$ 满足 $a_{i_1}<a_{i_2}<a_{i_3}<a_{i_4}$，然后从 $i_1$ 依次跳到 $i_4$。

现在有 $q$ 个事件：

1. 柱子 $i$ 的高度被修改为 $y$。
2. 只有编号 $[l,r]$ 的柱子可以被使用，小 D 想知道他能否完成一次施法。为了防止你蒙一个答案，实际询问时只会给定 $l$，你需要回答最小的 $r$，使得使用 $[l,r]$ 的柱子可以完成一次施法。特别地，如果不存在这样的 $r$，输出 $-1$。

输入格式

第一行两个正整数 $n,q$，表示柱子的数量与询问的数量。

第二行 $n$ 个正整数 $a_i$，表示初始柱子的高度。

接下来 $q$ 行每行描述一个询问：

• 如果第一个数为 $1$，接下来输入两个整数 $i,y$，表示将 $a_i$ 修改为 $y$。
• 如果第一个数为 $2$，接下来输入一个整数 $l$，表示询问一次 $l$ 的答案。

输出格式

对于每次操作 $2$，输出一行一个整数，表示最小的合法的 $r$。

样例

样例 1 输入

11 10
1 2 3 4 5 10 9 8 7 6 8
2 1
1 3 2
2 1
1 1 2
2 1
2 5
2 6
1 9 6
1 10 7
2 5

样例 1 输出

4
5
6
-1
-1
11

附加样例

见下发文件，第 $i$ 组下发样例符合第 $i$ 个子任务的限制。

数据范围与约定

对于全部数据，$1\le n,q\le 5\times 10^5,1\le a_i,y\le 10^9,1\le i,l\le n$