Немає часу малювати#11199
Бесі нещодавно отримала набір фарб і хоче розмалювати довгу огорожу з одного боку свого пасовища. Огорожа складається з послідовних -метрових сегментів. У Бесі є фарби різних кольорів, які вона позначила літерами від 'A' до 'Z' у порядку зростання темряви ('A' - найсвітліший колір, 'Z' - найтемніший). Таким чином, вона може описати розфарбування огорожі як рядок з символів (де кожен символ - це одна з літер від 'A' до 'Z').
Спочатку всі сегменти огорожі не розфарбовані. Бесі може розфарбувати будь-який неперервний діапазон сегментів одним кольором за одне доторкання пензля, причому вона ніколи не фарбує світлішим поверх темнішого (вона може фарбувати темнішим поверх світлішого).
Наприклад, спочатку не пофарбований відрізок довжини вона може пофарбувати так:
.... -> BBB. -> BBLL -> BQQLОбмежена в часі, Бесі може залишити деякі послідовні відрізки не пофарбованими. Зараз вона розглядає кандидатів відрізків, кожен задається двома цілими числами (, ) (1 \le a \le b \le n), що вказують індекси кінцевих точок відрізка, які повинні залишитися не пофарбованими.
Для кожного кандидата вкажіть мінімальну кількість доторкань, яка потрібна, щоб пофарбувати всі сегменти поза цим діапазоном у бажаний колір, залишаючи сегменти всередині діапазону не пофарбованими. Зазначимо, що Бесі насправді нічого не фарбує, тому відповіді для кожного діапазону-кандидата незалежні.
Перший рядок містить (1 \le n \le 10^5) і (1 \le q \le 10^5).
Наступний рядок містить рядок довжини , що представляє бажаний колір кожного сегмента огорожі.
Кожен з наступних рядків містить два цілі числа і , які представляють діапазон сегментів, що можливо залишаться не пофарбованими.
Для кожного з кандидатів виведіть відповідь на новому рядку.
У цьому прикладі, виключення діапазону відповідає бажаному зразку. У цьому прикладі виключення діапазону BAAB вимагає чотири доторкання для фарбування, а виключення діапазону ABBA - лише три.
.... -> AA.. -> ABBB -> ABCBПриклад 1