题目描述

在一条街上有 $n$ 栋建筑，从 $1$ 到 $n$ 编号。每栋建筑都包含一个披萨店和一个公寓。第 $k$ 栋建筑的披萨价格为 $p_k$。

你可以从任意一栋建筑的披萨店点餐到你所在的建筑。若你在第 $b$ 栋建筑，从第 $a$ 栋披萨店订餐，那么总价格为 $p_a + |a - b|$（即披萨价格加上送餐距离）。

现在你需要处理 $q$ 个操作，每个操作为以下两种之一：

• 将第 $k$ 栋建筑的披萨价格修改为 $x$；
• 你在第 $k$ 栋建筑，想知道订餐的最小总价格。

输入格式

第一行包含两个整数 $n,q$，表示建筑数量和操作数量。

第二行包含 $n$ 个整数 $p_1,p_2,\dots,p_n$，表示初始的披萨价格。

接下来 $q$ 行，每行描述一个操作，格式如下：

• 1 k x 表示将第 $k$ 栋的披萨价格修改为 $x$；
• 2 k 表示你在第 $k$ 栋，询问最便宜的订餐价格。

输出格式

对于每个类型为 2 的操作，输出一行一个整数，表示最小总价格。

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

5
4

数据规模与约定

初始状态下，位置 $2$ 最便宜的是从位置 $3$ 订餐，价格为 $4 + |3-2| = 5$。
修改后，第 $5$ 栋价格为 $1$，从第 $5$ 栋订餐到第 $2$ 栋只需 $1 + 3 = 4$。

• 对于 $100\%$ 的数据，$1 \le n, q \le 2 \times 10^5$，$1 \le p_i, x \le 10^9$，$1 \le k \le n$。