Đếm đoạn con không giảm

Cho dãy số nguyên dương $a_1,a_2,\dots ,a_n$. Bạn cần xử lý $q$ truy vấn thuộc hai dạng:

• 1 x y — Cập nhật $a_x:=y$.
• 2 l r — Đếm số cặp $(p,q)$ thỏa mãn $l\le p\le q\le r$ và đoạn con $a_p,a_{p+1},\dots ,a_q$ là không giảm, tức là $a_p\le a_{p+1}\le \dots \le a_q$.

Với mỗi truy vấn dạng 2, in ra số lượng cặp tìm được.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $q$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.
• $q$ dòng tiếp theo, mỗi dòng mô tả một truy vấn theo định dạng trên.

Dữ liệu ra

Với mỗi truy vấn dạng 2, in ra một dòng chứa câu trả lời.

Ràng buộc

• $1\le n,q\le 2·{10}^5$
• $1\le a_i\le {10}^9$
• Với truy vấn dạng 1: $1\le x\le n$, $1\le y\le {10}^9$.
• Với truy vấn dạng 2: $1\le l\le r\le n$.
• Có ít nhất một truy vấn dạng 2.

Ví dụ