Cho dãy \(a_1, a_2, ..., a_n\). Bạn cần thực hiện hai loại truy vấn sau:

• \(!\ u\ v\): Gán \(a_u = v\) \((1 \le u \le n, 1 \le v \le 10^9)\).
• \(?\ l\ r\): Giả sử mỗi thao tác bạn có thể chọn một phần tử bất kỳ và tăng giá trị của nó lên \(1\). Tính số lượng thao tác tối thiểu để dãy \(a_l, a_{l + 1}, ..., a_r\) là dãy không giảm.

Input

• Dòng đầu tiên gồm hai số nguyên dương \(n, q\) - số phần tử của dãy và số truy vấn cần xử lý (\(1 \le n, q \le 10^5\)).
• Dòng tiếp theo gồm \(n\) số nguyên dương \(a_1, a_2, ..., a_n\) (\(1 \le a_i \le 10^9\)).
• \(q\) dòng tiếp theo, mỗi dòng là một truy vấn thuộc một trong hai dạng trên.

Output

• Với mỗi truy vấn loại 2, in ra kết quả trên một dòng.

Example

4 3
2 4 1 4
? 2 4
! 1 4
? 1 4

3
3

Scoring

• \(20\%\) số điểm có \(n, q \le 2000\).
• \(30\%\) số điểm khác không có truy vấn loại 1.
• \(30\%\) số điểm khác có \(l = 1, r = n\) với mọi truy vấn loại 2.
• \(20\%\) số điểm còn lại không có giới hạn gì thêm.