Truy vấn Pizzeria

Có $n$ tòa nhà trên một con phố, tòa thứ $i$ có giá pizza là $p_i$. Chi phí đặt pizza từ tòa $a$ đến tòa $b$ là $p_a+|a-b|$. Xử lý $q$ truy vấn:

• 1 k x — Thay đổi giá pizza của tòa $k$ thành $x$.
• 2 k — Tìm chi phí nhỏ nhất để đặt pizza khi đang ở tòa $k$ (có thể đặt từ bất kỳ tòa nào).

Dữ liệu vào

• Dòng đầu: hai số nguyên $n$ và $q$.
• Dòng thứ hai: $n$ số nguyên $p_1,p_2,\dots ,p_n$.
• $q$ dòng tiếp theo: mỗi dòng là 1 k x hoặc 2 k.

Dữ liệu ra

Với mỗi truy vấn loại 2, in ra một dòng chứa chi phí nhỏ nhất.

Ràng buộc

• $1\le n,q\le 2\times {10}^5$
• $1\le p_i,x\le {10}^9$
• $1\le k\le n$

Ví dụ