WOMBO COMBO

Trong một trò chơi đối kháng, nhân vật của Prototype sở hữu một danh sách gồm \(N\) kỹ năng, kỹ năng thứ \(i\) có cấp độ sức mạnh là \(A[i]\). Để kích hoạt nội tại "Tuyệt kỹ tối thượng", Prototype cần tung ra một chuỗi combo gồm các chiêu thức từ trái sang phải sao cho chiêu thức sau phải có cấp độ sức mạnh lớn hơn hẳn chiêu thức trước.Tùy thuộc vào trang bị thay đổi trong trận đấu, cấp độ của các kỹ năng có thể tăng hoặc giảm. Hãy giúp Prototype xử lý \(Q\) yêu cầu:
Dạng 1: 1 i x : Kỹ năng thứ \(i\) được cường hóa hoặc giảm sức mạnh, thay đổi cấp độ thành \(x\).
Dạng 2: 2 l r : Trong tình huống giao tranh căng thẳng, Prototype chỉ có thể chọn các kỹ năng thuộc đoạn từ \(l\) đến \(r\). Hãy tính số lượng kỹ năng tối đa có thể đưa vào chuỗi combo tăng nghiêm ngặt này.

Yêu cầu: Hãy xử lý lần lượt \(Q\) truy vấn cập nhật và tìm độ dài dãy con tăng nghiêm ngặt dài nhất trong đoạn \([l, r]\). Với mỗi truy vấn dạng 2, in kết quả trên một dòng.

Input:

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(Q\) (\(1 \le N, Q \le 10^5\)) — lần lượt là số lượng kỹ năng và số lượng yêu cầu cần xử lý.
• Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, \dots, A_N\) (\(|A_i| \le 10^9\)) — trong đó \(A_i\) là cấp độ sức mạnh ban đầu của kỹ năng thứ \(i\).
• Q dòng tiếp theo, mỗi dòng là một truy vấn dạng 1 hoặc 2

Output:

• Với mỗi yêu cầu dạng 2, in ra một số nguyên duy nhất trên một dòng là số lượng kỹ năng tối đa thỏa mãn yêu cầu.

Example

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

3
3

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

2
1

Ràng buộc

• Subtask 1 (20% điểm): \(1 ≤ N, Q ≤ 200\).
• Subtask 2 (80% điểm): \(1 ≤ N, Q ≤ 10^5\).