Это усложненная версия задачи. Единственная разница между двумя версиями состоит в том, что более сложная версия дополнительно требует минимального количества подотрезков.
У Tokitsukaze есть двоичная строка \(s\) длины \(n\), состоящая только из нулей и единиц, \(n\) является четным.
Теперь Tokitsukaze делит \(s\) на минимальное количество непрерывных подотрезков, так чтобы в каждом подотрезке все биты были одинаковы. После этого \(s\) считается хорошей, если длины всех подотрезков четны.
Например, если \(s\) равна «11001111», она будет разделена на «11», «00» и «1111». Их длины равны \(2\), \(2\), \(4\) соответственно, все числа четные, поэтому «11001111» хорошая. Другой пример, если \(s\) равна «1110011000», она будет разделена на «111», «00», «11» и «000», а их длины равна \(3\), \(2\), \(2\), \(3\). Очевидно, что «1110011000» не является хорошей.
Tokitsukaze хочет улучшить \(s\), изменив значения некоторых позиций в \(s\). В частности, она может выполнить операцию любое количество раз: изменить значение \(s_i\) на «0» или «1» (\(1 \leq i \leq n\)). Можете ли вы назвать ей минимальное количество операций, чтобы сделать \(s\) хорошей? При этом она также хочет знать минимальное количество подотрезков, на которые можно разделить \(s\), среди всевозможных решений, которые используют минимальное количество операций.
Выходные данные
Для каждого набора входных данных выведите в одной строке два целых числа — минимальное количество операций, чтобы сделать \(s\) хорошей, и минимальное количество подотрезков, на которые можно разделить \(s\), среди всевозможных решений, которые используют минимальное количество операций.
Примечание
В первом наборе входных данных один из способов сделать \(s\) хорошей следующий.
Измените \(s_3\), \(s_6\) и \(s_7\) на «0», после чего \(s\) станет «1100000000», ее можно разделить на «11» и «00000000», длина которых составляет \(2\) и \(8\) соответственно, количество ее подотрезков равно \(2\). Существуют и другие способы использовать \(3\) операции, чтобы сделать \(s\) хорошей, например можно в итоге получить «1111110000», «1100001100», «1111001100», число подотрезков которых равно \(2\), \(4\), \(4\) соответственно. Легко заметить, что минимальное количество подотрезков среди всего минимального числа решений операций равно \(2\).
Во втором, третьем и четвертом наборах входных данных \(s\) изначально хорошая, поэтому никаких действий не требуется.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
10
1110011000
8
11001111
2
00
2
11
6
100110
|
3 2
0 3
0 1
0 1
3 1
|