Bessie vừa nhận được 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 dài 1 mét ($1\le N\le 10^5$). Bessie có 26 màu khác nhau, đánh dấu bằng các chữ cái từ 'A' đến 'Z' theo thứ tự tăng dần độ tối ('A' rất sáng, còn 'Z' rất tối). Vì thế, cô có thể mô tả màu mong muốn của mỗi đoạn bằng một chuỗi độ dài $N$ mà mỗi ký tự là một chữ cái.
Ban đầu, tất cả các đoạn đều chưa có màu. Bessie có thể sơn bất kỳ khoảng liên tiếp nào bằng một màu duy nhất trong một lượt quét cọ, miễn là không bao giờ sơn màu sáng hơn lên màu tối hơn (chỉ được sơn màu tối hơn lên màu sáng hơn).
Ví dụ, một đoạn ban đầu chưa có màu với độ dài bốn có thể được tô như sau:
.... -> BBB. -> BBLL -> BQQL
Không còn nhiều thời gian, Bessie nghĩ rằng có lẽ cô phải để một khoảng liên tiếp của hàng rào chưa sơn! Hiện cô cân nhắc $Q$ khoảng ứng viên ($1\le Q\le 10^5$), mỗi khoảng được mô tả bằng hai số nguyên $(a,b)$ với $1 \leq a \leq b \leq N$, cho biết chỉ số hai đầu của khoảng $a \ldots b$ sẽ để chưa sơn.
Với mỗi khoảng ứng viên, cần ít nhất bao nhiêu lượt quét cọ để sơn mọi đoạn bên ngoài khoảng thành màu mong muốn, đồng thời giữ tất cả các đoạn bên trong không có màu? Lưu ý rằng Bessie không thực sự sơn trong quá trình này, nên đáp án cho từng khoảng ứng viên là độc lập.
Dữ liệu vào
Dòng đầu tiên chứa $N$ và $Q$.
Dòng tiếp theo chứa một chuỗi độ dài $N$ biểu diễn màu mong muốn cho mỗi đoạn hàng rào.
Mỗi dòng trong $Q$ dòng tiếp theo chứa hai số nguyên $a$ và $b$ cách nhau bởi dấu cách, biểu diễn một khoảng ứng viên có thể để chưa sơn.
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.
Ví dụ
Dữ liệu vào 1
8 2 ABBAABCB 3 6 1 4
Dữ liệu ra 1
4 3
Ghi chú
Trong ví dụ này, loại bỏ khoảng con tương ứng với mẫu mong muốn $\texttt{BAAB}$ cần bốn lượt quét cọ để sơn, còn loại bỏ $\texttt{ABBA}$ chỉ cần ba lượt.
.... -> AA.. -> ABBB -> ABCB
Nhiệm vụ con
- Các trường hợp kiểm thử 1–4 thỏa mãn $N,Q\le 100$.
- Các trường hợp kiểm thử 5–7 thỏa mãn $N,Q\le 5000$.
- Các trường hợp kiểm thử 8–13 không có giới hạn bổ sung.
Tác giả bài toán: Andi Qu và Brian Dean