Mô tả bài toán: Truy vấn giá pizza

Có ~n~ tòa nhà trên một con đường, đánh số từ 1 đến ~n~. Mỗi tòa nhà có một quán pizza và một căn hộ.

Giá pizza tại tòa nhà ~k~ là ~p_k~. Nếu bạn đặt một chiếc pizza từ tòa nhà ~a~ đến tòa nhà ~b~, giá của nó (bao gồm phí giao hàng) là ~p_a + |a - b|~.

Nhiệm vụ của bạn là xử lý hai loại truy vấn:

1. Cập nhật giá pizza: Giá pizza ~p_k~ tại tòa nhà ~k~ trở thành ~x~.
2. Tìm giá thấp nhất: Bạn đang ở tòa nhà ~k~ và muốn đặt một chiếc pizza. Giá thấp nhất là bao nhiêu?

Input:

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~q~: số lượng tòa nhà và số lượng truy vấn.
• Dòng thứ hai chứa ~n~ số nguyên ~p_1, p_2, ..., p_n~: giá pizza ban đầu tại mỗi tòa nhà.
• Sau đó có ~q~ dòng, mỗi dòng mô tả một truy vấn:
  • 1 k x: Cập nhật giá pizza tại tòa nhà ~k~ thành ~x~.
  • 2 k: Tìm giá thấp nhất cho tòa nhà ~k~.

Output:

• Với mỗi truy vấn loại 2, in ra giá thấp nhất.

Ràng buộc:

• ~1 \leq n, q \leq 2 \cdot 10^5~
• ~1 \leq p_i, x \leq 10^9~
• ~1 \leq k \leq n~

Ví dụ:

Input:

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

Output:

5
4