Lúc đang chơi Domino thì ledinhbaonam bất ngờ nảy ra một trò chơi mới.

Cậu xếp \(N\) quân Domino thành một hàng dài. Trên mỗi quân Domino có ghi một số nguyên, quân thứ \(i\) mang giá trị \(A_i\).

Sau một lúc quan sát, ledinhbaonam nhận thấy có những đoạn Domino trông rất đẹp. Cậu định nghĩa rằng một đoạn liên tiếp từ vị trí \(l\) đến vị trí \(r\) là một đoạn Domino nếu độ chênh lệch giữa giá trị lớn nhất và nhỏ nhất trong đoạn đúng bằng khoảng cách giữa hai đầu đoạn.

Cụ thể, gọi:

Đoạn \([l,r]\) được gọi là Domino nếu:

Nghe qua thì khá đơn giản, nhưng trò chơi nhanh chóng trở nên thú vị hơn khi ledinhbaonam liên tục thay đổi giá trị trên các quân Domino.

Mỗi khi một quân Domino bị thay đổi, toàn bộ những đoạn Domino trước đó có thể không còn hợp lệ nữa.

Vì vậy uia liên tục đặt ra các câu hỏi:

• Thay đổi giá trị của một quân Domino.
• Đếm xem trong một đoạn bàn chơi cho trước có bao nhiêu đoạn Domino.

Do số lượng câu hỏi khá lớn nên uia đã nhờ npgb và các bạn coders giúp đỡ.

Nhiệm vụ

Bạn cần xử lý \(Q\) truy vấn thuộc một trong hai loại sau:

• 1 p x: Gán \(A_p=x\).
• 2 l r: Đếm số đoạn Domino nằm hoàn toàn bên trong đoạn \([l,r]\).

Input

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(Q\). (\(1 \le N \le 1000\), \(1 \le Q \le 5000\))
• Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, \dots, A_N\). (\(1 \le A_i \le 10^{18}\))
• \(Q\) dòng tiếp theo, mỗi dòng mô tả một truy vấn theo đúng định dạng đã nêu.

Output

• Với mỗi truy vấn loại 2, in ra trên một dòng duy nhất số lượng đoạn Domino tương ứng.

Example

5 2
3 1 2 5 4
2 1 5
2 2 4

9
4

4 3
1 2 4 3
2 1 4
1 3 3
2 1 4

8
6