У вас есть бинарная строка \(a\) длины \(n\), состоящая только из цифр \(0\) и \(1\).
Вам даны \(q\) запросов. В \(i\)-м запросе даны два индекса \(l\) и \(r\) такие, что \(1 \le l \le r \le n\).
Пусть \(s=a[l,r]\). Вам разрешено выполнять следующую операцию над \(s\):
- Выберите два индекса \(x\) и \(y\) такие, что \(1 \le x \le y \le |s|\). Пусть \(t\) — подстрока \(t = s[x, y]\). Тогда для всех \(1 \le i \le |t| - 1\) должно выполняться условие \(t_i \neq t_{i+1}\). Заметим, что \(x = y\) всегда является допустимой подстрокой.
- Удалите подстроку \(s[x, y]\) из \(s\).
Для каждого из \(q\) запросов найдите минимальное количество операций, необходимое для превращения \(s\) в пустую строку.
Напомним, что для строки \(s\), \(s[l,r]\) обозначает подотрезок \(s_l,s_{l+1},\ldots,s_r\).
Выходные данные
Выведите \(q\) строк, в \(i\)-й строке выведите минимальное количество операций, необходимых для \(i\)-го запроса.
Примечание
В первом примере,
- Подстрока равна \(\texttt{101}\), поэтому мы можем сделать одну операцию, чтобы сделать подстроку пустой.
- Подстрока равна \(\texttt{11011}\), поэтому мы можем сделать одну операцию над \(s[2, 4]\), чтобы получить \(\texttt{11}\), а затем использовать еще две операции, чтобы сделать подстроку пустой.
- Подстрока — \(\texttt{011}\), поэтому мы можем сделать одну операцию над \(s[1, 2]\), чтобы получить \(\texttt{1}\), а затем использовать еще одну операцию, чтобы сделать подстроку пустой.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 3
11011
2 4
1 5
3 5
|
1
3
2
|
|
2
|
10 3
1001110110
1 10
2 5
5 10
|
4
2
3
|