You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

翻译自 CSES-2206 题。

题目描述

街道上有 $n$ 栋建筑，编号为 $1,2,...,n$。每栋建筑都有一个披萨店和一间公寓。

第 $k$ 栋建筑的披萨价格为 $p_k$。如果你从建筑 $a$ 订购披萨送到建筑 $b$，其价格（包括配送费用）为 $p_a+∣a−b∣$，其中 $∣a−b∣$ 是建筑 $a$ 到建筑 $b$ 的距离。

你的任务是处理两种类型的查询：

1. 更新建筑 $k$ 的披萨价格为 $x$。
2. 你在建筑 $k$ 并想订购披萨，询问最低的披萨价格是多少。

输入格式

第一行包含两个整数 $n$ 和 $q$：分别表示建筑的数量和查询的数量。

第二行包含 $n$ 个整数 $p_1,p_2,…,p_n$：表示每栋建筑初始的披萨价格。

接下来有 $q$ 行描述查询。每一行是以下两种之一：

• 1 k x：将建筑 $k$ 的披萨价格更新为 $x$。
• 2 k：你在建筑 $k$，询问从建筑 $k$ 订购披萨的最低价格。

输出格式

对于每个查询类型为 2 的查询，输出一个整数，即从建筑 $k$ 订购披萨的最低价格。

样例

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

5
4

说明/提示

$1 \leq n,q \leq 2 \cdot 10^5$；

$1 \leq p_i,x \leq 10^9$；

$1 \leq k \leq n$。