F. I Might Be Wrong
binary search; greedy; two pointers
You are given a binary string \(S\) of length \(n\) indexed from \(1\) to \(n\). You can perform the following operation any number of times (possibly zero):Choose two integers \(l\) and \(r\) (\(1 \le l \le r \le n\)). Let \(cnt_0\) be the number of times 0 occurs in \(S[l \ldots r]\) and \(cnt_1\) be the number of times 1 occurs in \(S[l \ldots r]\). You can pay \(|cnt_0 - cnt_1| + 1\) coins and sort the \(S[l \ldots r]\). (by \(S[l \ldots r]\) we mean the substring of \(S\) starting at position \(l\) and ending at position \(r\))For example if \(S = \) 11001, we can perform the operation on \(S[2 \ldots 4]\), paying \(|2 - 1| + 1 = 2\) coins, and obtain \(S = \) 10011 as a new string.Find the minimum total number of coins required to sort \(S\) in increasing order.
The first line contains a single integer \(t\) (\(1 \le t \le 1000\)) — the number of test cases. The description of test cases follows.The first line of each test case contains a single integer \(n\) (\(1 \le n \le 2 \cdot 10^5\)) — the size of \(S\).The second line of each test case contains a binary string \(S\) of \(n\) characters \(S_1S_2 \ldots S_n\). (\(S_i = \) 0 or \(S_i = \) 1 for each \(1 \le i \le n\))It is guaranteed that the sum of \(n\) over all test cases doesn't exceed \(2 \cdot 10^5\).
For each test case, output the minimum total number of coins required to sort \(S\) in increasing order.
In the first test case, \(S\) is already sorted.In the second test case, it's enough to apply the operation with \(l = 1, r = 2\).In the third test case, it's enough to apply the operation with \(l = 1, r = 2\).