Назовем бинарную строку \(T\) длины \(m\), индексированную от \(1\) до \(m\) параноидальной, если мы можем получить строку длины \(1\), выполнив следующие два вида операций \(m-1\) раз в любом порядке:
- Выберите любую подстроку \(T\), которая равна 01, и замените ее на 1.
- Выберите любую подстроку \(T\), которая равна 10, а затем замените ее на 0.
Например, если \(T = \) 001, мы можем выбрать подстроку \([T_2T_3]\) и выполнить первую операцию. Таким образом, мы получим \(T = \) 01 в качестве новой строки.
Вам дана бинарная строка \(S\) длины \(n\), индексированная от \(1\) до \(n\). Найдите количество пар целых чисел \((l, r)\) с \(1 \le l \le r \le n\) таких, что \(S[l \ldots r]\) (подстрока \(S\) от \(l\) до \(r\)) является параноидальной строкой.
Выходные данные
Для каждого набора входных данных выведите количество пар целых чисел \((l, r)\) с \(1 \le l \le r \le n\) таких, что \(S[l \ldots r]\) (подстрока \(S\) от \(l\) до \(r\)) является параноидальной строкой.
Примечание
В первом примере \(S\) уже имеет длину \(1\) и нет нужды ни в каких операциях.
Во втором примере все подстроки \(S\) являются параноидальными. Для всей строки достаточно выполнить первую операцию.
В третьем примере все подстроки \(S\) являются параноидальными, кроме \([S_2S_3]\), потому что мы не можем выполнить над ней никаких операций, и \([S_1S_2S_3]\) (всей строки).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1
1
2
01
3
100
4
1001
5
11111
|
1
3
4
8
5
|