Cho hoán vị \(A=[A_1,\ldots,A_N]\). Một lần biến đổi của dãy \(B=[B_1,\ldots,B_K]\) là xóa đồng thời mọi phần tử \(B_i\) với \(2\le i<K\) và \(B_{i-1}>B_i<B_{i+1}\), rồi ghép các phần tử còn lại theo thứ tự cũ.

Với mỗi truy vấn \((l,r,t)\), hãy tìm số phần tử còn lại của dãy \([A_l,\ldots,A_r]\) sau \(t\) lần biến đổi.

Dữ liệu vào

• Dòng đầu chứa \(N,Q\).
• Dòng thứ hai chứa hoán vị \(A\).
• \(Q\) dòng tiếp theo chứa \(l,r,t\).

Dữ liệu ra

In \(Q\) dòng theo thứ tự dữ liệu vào; dòng thứ \(j\) là câu trả lời cho truy vấn thứ \(j\).

Ràng buộc

• \(1\le N,Q\le200000\).
• \(A\) là hoán vị của \(1,\ldots,N\).
• \(1\le l\le r\le N\), \(1\le t\le N\).

Phân nhóm

• Nhóm 1 (6 điểm): \(N\le5000\) và mọi truy vấn có \(l=1,r=N\).
• Nhóm 2 (11 điểm): mọi truy vấn có \(l=1,r=N\).
• Nhóm 3 (6 điểm): \(t=1\) với mọi truy vấn.
• Nhóm 4 (12 điểm): \(t=N\) với mọi truy vấn.
• Nhóm 5 (7 điểm): tồn tại \(p\) (\(1\le p\le N\)) sao cho \(A_i>A_{i+1}\) với mọi \(1\le i<p\) và \(A_i<A_{i+1}\) với mọi \(p\le i<N\).
• Nhóm 6 (26 điểm): sau 20 lần biến đổi toàn bộ \(A\), dãy không còn thay đổi.
• Nhóm 7 (32 điểm): Không có ràng buộc bổ sung.

Ví dụ

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

3
2
3
3
2

15 7
14 5 2 7 11 13 3 12 9 4 10 8 1 6 15
1 15 1
1 15 2
1 15 3
1 15 4
1 15 5
1 15 6
1 15 7

11
8
6
4
3
2
2

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

8
6
2
3
5
3
4
3
2
3

Nguồn

KOI 2026 Round 2, problem Local Minimum Removal. Tài liệu, dữ liệu chấm và mã nguồn mẫu từ Korean Olympiad in Informatics, phát hành theo CC BY-NC-SA 4.0.