Có đúng một khối lập phương của mỗi kích thước từ \(1\) đến \(n\), màu P hoặc C. Một tháp hợp lệ có các khối theo thứ tự kích thước giảm dần từ dưới lên, và hai khối kề nhau không cùng màu. Với mỗi truy vấn \([l,r]\), hãy tìm số tháp nhỏ nhất để dùng tất cả các khối có kích thước trong đoạn đó.

Dữ liệu vào

Dòng đầu chứa \(n,q\) (\(1\le n,q\le10^5\)). Dòng hai là chuỗi \(s\) độ dài \(n\), mỗi ký tự là P hoặc C; \(s_i\) là màu khối kích thước \(i\). \(q\) dòng tiếp theo chứa \(l_i,r_i\) (\(1\le l_i\le r_i\le n\)).

Dữ liệu ra

Với mỗi truy vấn, in số tháp nhỏ nhất trên một dòng.

Ràng buộc

Các giới hạn chính thức của dữ liệu được nêu đầy đủ trong phần Dữ liệu vào.

Phân nhóm

1. \(23\) điểm: \(n,q\le10\).
2. \(38\) điểm: \(n,q\le1000\).
3. \(25\) điểm: có nhiều nhất \(20\) khối màu xanh.
4. \(24\) điểm: không có ràng buộc thêm.

Ví dụ

7 4
PPCPPCC
1 7
1 5
3 7
4 5

3
3
2
2

6 2
CCCCCC
1 6
2 5

6
4

16 1
PPPCPCCCCCCPPPPP
1 16

6

Nguồn

COCI 2025/2026 - Vòng 2, bài Tornjevi.

Đề bài, dữ liệu kiểm thử và lời giải tham khảo được lấy từ nguồn chính thức của Croatian Open Competition in Informatics.