题目描述

给定一个长度为 $n$ 的数列 $a_1, a_2, \ldots, a_n$。

接下来有 $m$ 次操作，操作分为如下两种类型：

• 1 p x：将 $a_p$ 的数值更新为 $x$；
• 2 l r：查询下标区间 $[l, r]$ 范围内所有数字（即 $a_l, a_{l+1}, \ldots, a_r$）的最小值。

对于每次查询操作，你需要输出对应的结果。

输入格式

第一行，一个整数 $n(1 \le n \le 10^5)$。

第二行，$n$ 个整数 $a_1, a_2, \ldots, a_n(1 \le a_i \le 10^9)$，表示初始时数列中每个元素的数值。

第三行，一个整数 $m(1 \le m \le 10^5)$，表示操作次数。

接下来 $m$ 行，每行包含一个操作：

• 1 p x（$1 \le p \le$），或
• 2 l r（$1 \le l \le r \le n$）

输出格式

对于每个查询操作 2 l r，输出一行，包含一个整数，表示下标区间 $[l, r]$ 范围内所有数字（即 $a_l, a_{l+1}, \ldots, a_r$）的最小值。

注：因为本题考察的知识点是数列分块，所以请尽量用分块来解决本题。

5
1 2 3 4 5
5
2 2 4
1 2 6
2 2 4
1 3 7
2 3 5

2
3
4

说明/提示

样例解释

• 初始时数列为 $\{ 1, 2, 3, 4, 5 \}$；
• 第 $1$ 个操作：$\min\{ a_2, a_3, a_4 \} = \min\{ 2, 3, 4 \} = 2$；
• 第 $2$ 个操作：$a_2 = 6$，数列更新为 $\{ 1, 6, 3, 4, 5 \}$；
• 第 $3$ 个操作：$\min\{ a_2, a_3, a_4 \} = \min\{ 6, 3, 4 \} = 3$；
• 第 $4$ 个操作：$a_3 = 7$，数列更新为 $\{ 1, 6, 7, 4, 5 \}$；
• 第 $5$ 个操作：$\min\{ a_3, a_4, a_5 \} = \min\{ 7, 4, 5 \} = 4$。

数据规模与约定

• 对于 $20\%$ 的数据，$n, m \le 10$
• 对于 $50\%$ 的数据，$n, m \le 1000$
• 对于 $100\%$ 的数据，$1 \le n, m \le 10^5; 1 \le a_i, x \le 10^9; 1 \le l \le r \le n; 1 \le p \le n$