Bessie недавно получила набор для рисования и хочет покрасить длинный забор на одном краю своего пастбища. Забор состоит из $N$ последовательных участков длиной 1 метр ($1\le N\le 10^5$). У Bessie есть 26 различных цветов, которые она обозначает буквами от 'A' до 'Z' в порядке увеличения темноты ('A' — очень светлый цвет, а 'Z' — очень тёмный). Поэтому желаемые цвета участков можно описать строкой длины $N$, каждый символ которой является буквой.
Изначально все участки не окрашены. Bessie может одним мазком покрасить любой непрерывный диапазон участков в один цвет, если она никогда не наносит более светлый цвет поверх более тёмного (поверх светлых цветов можно наносить только более тёмные).
Например, изначально неокрашенный участок длины четыре можно покрасить так:
.... -> BBB. -> BBLL -> BQQL
Времени мало, и Bessie думает, что ей, возможно, придётся оставить некоторый непрерывный диапазон участков забора неокрашенным! Сейчас она рассматривает $Q$ возможных диапазонов ($1\le Q\le 10^5$), каждый из которых задан двумя целыми числами $(a,b)$, где $1 \leq a \leq b \leq N$, указывающими номера концов диапазона $a \ldots b$, который нужно оставить неокрашенным.
Для каждого возможного диапазона определите минимальное число мазков, необходимое, чтобы покрасить каждый участок вне диапазона в желаемый цвет, оставив все участки внутри неокрашенными. Учтите, что в процессе Bessie ничего не красит в действительности, поэтому ответы для разных диапазонов независимы.
Входные данные
Первая строка содержит $N$ и $Q$.
Следующая строка содержит строку длины $N$, задающую желаемый цвет каждого участка забора.
Каждая из следующих $Q$ строк содержит два целых числа $a$ и $b$, разделённых пробелом, которые задают возможный диапазон для оставления неокрашенным.
Выходные данные
Для каждого из $Q$ вариантов выведите ответ в отдельной строке.
Примеры
Входные данные 1
8 2 ABBAABCB 3 6 1 4
Выходные данные 1
4 3
Примечание
В этом примере исключение поддиапазона с желаемым рисунком $\texttt{BAAB}$ требует четырёх мазков для покраски, тогда как исключение $\texttt{ABBA}$ требует только трёх.
.... -> AA.. -> ABBB -> ABCB
Подзадачи
- Тесты 1–4 удовлетворяют $N,Q\le 100$.
- Тесты 5–7 удовлетворяют $N,Q\le 5000$.
- В тестах 8–13 нет дополнительных ограничений.
Авторы задачи: Andi Qu и Brian Dean