Послідовні#11718
Вам дано рядок s = s_1 s_2 ... s_n довжини , що складається з малих літер англійського алфавіту.
Також вам надано запитів до рядка . Для кожного запиту i = 1, 2, ..., q, -й запит задається двома цілими числами l_i та r_i і формулюється наступним чином:
У підрядку s_{l_i} s_{l_{i+1}} ... s_{r_i} рядка , який охоплює символи з l_i-го по r_i-й, скільки є позицій, де одна і та ж мала літера англійського алфавіту зустрічається двічі поспіль? Іншими словами, скільки існує цілих чисел , таких що l_i \le p \le r_{i}-1 і s_p = s_{p+1}?
Виведіть відповідь для кожного з запитів.
Перша строка містить два цілі числа та q~(1 \le n, q \le 3 \cdot 10^5).
У другому рядку задано рядок довжини , що складається з малих літер англійського алфавіту.
Кожна з наступних строк містить запит (l_i, r_i), 1 \le l_i, r_i \le n, 1 \le i \le q.
Виведіть строк. Для кожного i = 1, 2, ..., q, -та строка повинна містити відповідь на -й запит.
Приклад 1
Приклад 2