Вам дана бинарная строка \(s\) длины \(n\). Определим максимальную подстроку как подстроку, которую нельзя расширить, сохраняя при этом все элементы равными. Например, в строке \(11000111\) есть три максимальные подстроки: \(11\), \(000\) и \(111\).
За одну операцию можно выбрать две максимальные соседние подстроки. Поскольку они максимальные и соседние, легко видеть, что их элементы должны иметь разные значения. Пусть \(a\) — длина последовательности единиц, а \(b\) — длина последовательности нулей. Затем сделайте следующее:
- Если \(a \ge b\), то заменить \(b\) выбранных нулей на \(b\) единиц.
- Если \(a < b\), то заменить \(a\) выбранных единиц на \(a\) нулей.
Например, для \(1110000\) мы превратим в \(0000000\), для \(0011\) мы превратим в \(1111\). Мы называем строку хорошей, если ее можно превратить в \(1111...1111\) с помощью применения вышеупомянутой операции произвольное количество раз (возможно, ноль). Найдите количество хороших подстрок среди всех \(\frac{n(n+1)}{2}\) непустых подстрок \(s\).
Выходные данные
Для каждого теста выведите одно целое число — количество хороших подстрок.
Примечание
Определим подстроку от индекса \(l\) до индекса \(r\) как \([l, r]\).
Для первого теста хорошими подстроками являются:
- \([1,1]\),
- \([1,2]\),
- \([3,6]\),
- \([4,5]\),
- \([4,6]\),
- \([5,5]\),
- \([5,6]\),
- \([6,6]\).
Во втором наборе входных данных все подстроки хорошие, кроме \([2,2]\).
В третьем наборе входных данных все подстроки хорошие.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
6
100011
3
101
5
11111
6
010101
|
8
5
15
18
|