题目背景

” 嘿！在星期五我们会有一场很棒的比赛。”

” 那就去呗...”

……

” 这道题也太难了，别人也肯定 A 不了的，这边好像还剩下一个简单点的，我们来看看这个。”

题目描述

小可可被给予了一个包含 $n$ 个正整数的数列 $a_1, a_2, \cdots, a_n$，并且满足 $a_i \in [1, k]$。

小可可将会收到 $m$ 条请求，请求有两种类型：

• 类型 $1$：1 p v，表示将 $a_p$ 修改为 $v$，保证 $1 \le p \le n, 1 \le v \le k$；
• 类型 $2$：2，表示需要求出一个最短的连续子数组，使其包含 $1, 2, 3, \cdots, k$ 中所有数，输出该子数组的长度。

如果不存在这样的子数组，则输出 -1。

• 说明：子数组必须是连续的一段区间。

输入格式

第一行输入三个整数 $n, k, m$，分别表示数列长度、数值范围以及操作次数。

第二行输入 $n$ 个整数 $a_1, a_2, \cdots, a_n$。

接下来 $m$ 行，每行表示一次操作，格式为 1 p v 或 2。

输出格式

对于每一个类型 $2$ 的请求，输出一行一个整数表示答案；若不存在满足条件的子数组，则输出 -1。

样例输入 1

4 3 5
2 3 1 2
2
1 3 3
2
1 1 1
2

样例输出 1

3
-1
4

样例输入 2

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

样例输出 2

3
3
4

说明

样例解释

对于样例 $1$：

• 第一次请求为 2，此时数列为 $[2, 3, 1, 2]$，包含 $1, 2, 3$ 所有数的最短连续子数组可以为 $[2, 3, 1]$，长度为 $3$。
• 第二次请求为 1 3 3，此时数列变为 $[2, 3, 3, 2]$。
• 第三次请求为 2，此时不存在包含全部 $1, 2, 3$ 的连续子数组。
• 第四次请求为 1 1 1，此时数列变为 $[1, 3, 3, 2]$。
• 第五次请求为 2，包含 $1, 2, 3$ 所有数的最短连续子数组可以为 $[1, 3, 3, 2]$，长度为 $4$。

其它样例说明

• 样例 3：测试用例见选手目录下的 contest/contest3.in 与 contest/contest3.ans，满足测试点 $3 \sim 5$ 的约束条件。
• 样例 4：测试用例见选手目录下的 contest/contest4.in 与 contest/contest4.ans，满足测试点 $10$ 的约束条件。

数据范围

对于 $100\%$ 的数据，$1 \le n, m \le 10^5$，$1 \le k \le 10^5$，$1 \le a_i \le k$。

各测试点的附加限制如下表所示：

点击下载大样例