Вам дана бинарная строка \(S\) длины \(n\), индексированная от \(1\) до \(n\). Вы можете выполнить следующую операцию любое количество раз (возможно, ноль):
Выберите два целых числа \(l\) и \(r\) (\(1 \le l \le r \le n\)). Пусть \(cnt_0\) это количество вхождений 0 в \(S[l \ldots r]\), а \(cnt_1\) это количество вхождений 1 в \(S[l \ldots r]\). Вы можете заплатить \(|cnt_0 - cnt_1| + 1\) монет и отсортировать \(S[l \ldots r]\). (Как \(S[l \ldots r]\) мы обозначаем подстроку \(S\), начинающуюся в позиции \(l\) и заканчивающуюся в позиции \(r\)).
Например, если \(S = \) 11001, мы можем выполнить операцию над \(S[2 \ldots 4]\) за \(|2 - 1| + 1 = 2\) монеты и получить \(S = \) 10011 в качестве новой строки.
Найдите минимальное общее количество монет, необходимое для сортировки \(S\) в возрастающем порядке.
Первая строка содержит одно целое число \(t\) (\(1 \le t \le 1000\)) — количество наборов входных данных. Далее следует описание наборов входных данныхв.
Первая строка каждого набора входных данных содержит одно целое число \(n\) (\(1 \le n \le 2 \cdot 10^5\)) — размер \(S\).
Вторая строка каждого набора входных данных содержит бинарную строку \(S\) из \(n\) символов \(S_1S_2 \ldots S_n\). (\(S_i = \) 0 или \(S_i = \) 1 для каждого \(1 \le i \le n\)).
Гарантируется, что сумма \(n\) по всем наборам входных данных не превышает \(2 \cdot 10^5\).
Для каждого набора входных данных выведите минимальное общее количество монет, необходимое для сортировки \(S\) в возрастающем порядке.
В первом наборе входных данных \(S\) уже отсортирована.
Во втором наборе входных данных достаточно применить операцию с \(l = 1, r = 2\).
В третьем наборе входных данных достаточно применить операцию с \(l = 1, r = 2\).
7 1 1 2 10 3 101 4 1000 5 11010 6 110000 20 01000010001010011000
0 1 1 3 2 2 5
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач