Gần đây Bessie được tặng một bộ dụng cụ vẽ và muốn sơn hàng rào dài ở một đầu đồng cỏ. Hàng rào gồm \(N\) đoạn liên tiếp, mỗi đoạn dài 1 mét (\(1\le N\le 10^5\)). Bessie có 26 màu khác nhau, được ký hiệu bằng các chữ cái từ A đến Z theo độ đậm tăng dần: A rất nhạt, còn Z rất đậm. Vì vậy, màu mong muốn của từng đoạn hàng rào được mô tả bằng một xâu độ dài \(N\).

Ban đầu, mọi đoạn hàng rào đều chưa được sơn. Trong một nét cọ, Bessie có thể tô một đoạn liên tiếp bất kỳ bằng một màu duy nhất, miễn là cô không bao giờ sơn màu nhạt hơn lên trên màu đậm hơn; cô chỉ có thể phủ màu đậm lên màu nhạt.

Ví dụ, một đoạn chưa tô có độ dài bốn có thể được sơn như sau:

.... -> BBB. -> BBLL -> BQQL

Vì sắp hết thời gian, Bessie có thể phải để nguyên một đoạn liên tiếp không sơn. Cô đang xét \(Q\) đoạn ứng viên (\(1\le Q\le 10^5\)), mỗi đoạn được mô tả bởi hai số nguyên \((a,b)\) với \(1\le a\le b\le N\), là hai đầu mút của đoạn \(a\ldots b\) cần để trống.

Với mỗi đoạn ứng viên, hãy tính số nét cọ ít nhất để sơn mọi đoạn hàng rào nằm ngoài đoạn đó đúng màu mong muốn, đồng thời giữ mọi đoạn bên trong chưa sơn. Bessie không thực sự sơn trong quá trình này, nên đáp án của các ứng viên độc lập với nhau.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(Q\).

Dòng tiếp theo chứa một xâu độ dài \(N\), biểu diễn màu mong muốn của từng đoạn hàng rào.

\(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(a\) và \(b\), cách nhau bởi dấu cách, mô tả một đoạn ứng viên cần để trống.

Dữ liệu ra

Với mỗi ứng viên trong \(Q\) ứng viên, in đáp án trên một dòng mới.

Phân nhóm

• Các test 1-4 thỏa mãn \(N,Q\le 100\).
• Các test 5-7 thỏa mãn \(N,Q\le 5000\).
• Các test 8-13 không có ràng buộc bổ sung.

Ví dụ

8 2
ABBAABCB
3 6
1 4

4
3

.... -> AA.. -> ABBB -> ABCB

Nguồn

USACO 2021 January Contest, Silver - No Time to Paint: https://usaco.org/index.php?page=viewproblem2&cpid=1087

Tác giả: Andi Qu và Brian Dean.