I Might Be Wrong
Contest: Codeforces Round 800 (Div. 1)
Difficulty rating: 3400
Tags: 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.

Input format:
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$$$.

Output format:
For each test case, output the minimum total number of coins required to sort $$$S$$$ in increasing order.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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$$$.

Example input:
7
1
1
2
10
3
101
4
1000
5
11010
6
110000
20
01000010001010011000

Example output:
0
1
1
3
2
2
5

Editorial:
- It's trivial that we only sort with segments with balance $$$0$$$.
Proof: Imagine we have sorted interval $$$[l, r]$$$ and it has $$$d$$$ more zeros than it has ones. So this operation costs $$$d + 1$$$ coins. $$$S_l$$$ has to be $$$1$$$ otherwise we could just sort $$$[l + 1, r]$$$ with $$$d$$$ coins.
Now that we know $$$S_l$$$ is $$$1$$$ there exists some $$$k \leq r$$$ that the interval $$$[l, k]$$$ has equal number of zeros and ones. Because the interval $$$[l, l]$$$ has more ones but the interval $$$[l, r]$$$ has more zeros.
Sort $$$[l, k]$$$ with cost $$$1$$$ and then sort $$$[l + 1, r]$$$ with cost $$$d$$$. And we know we can sort $$$[l + 1, r]$$$ such that we only sort segments with balance $$$0$$$.
- If everything is sorted cool. Suppose now the number of ones is greater than the number of zeros.
- Replace $$$0$$$ by $$$-1$$$, $$$1$$$ by $$$1$$$, draw prefix sums. We have $$$n + 1$$$ points $$$(i, a_i)$$$, (initially $$$a_i = pref_i$$$), where $$$a_0 = 0$$$, $$$a_n>0$$$, and the operation is: choosing $$$i$$$, $$$j$$$ such that $$$a_i = a_j$$$ and making points between them first decrease then increase.
Denote by AmShZ strategy the following procedure: while $$$S$$$ isn't sorted,
• Let $$$i$$$ be the smallest such that numbers from $$$a_i$$$ to $$$a_n$$$ increase.
• If $$$a_i \leq 0$$$, we sort in $$$1$$$ operation.
• Otherwise, let $$$j$$$ be the smallest such that $$$a_j = a_i$$$. Apply operation to $$$[j, i]$$$.
Let's denote by $$$f(S)$$$ the smallest number of operations required for the current configuration. We will prove that AmShZ strategy ends in $$$f(S)$$$ iterations by induction over $$$n$$$ and over number of inversions in $$$S$$$. (Clearly any non-identical operation decreases number of inversions so that's useful).
Denote by $$$S_k$$$ string $$$S$$$ in which suffix of length $$$k$$$ is sorted.
Lemma 1: If $$$k1 > k2$$$, then AmShZ strategy for $$$S_{k1}$$$ uses at most as many operations as for $$$S_{k2}$$$. Proof: trivial
Suppose now that we have proved our statement for all strings with the number of inversions less than in $$$S$$$.
Now, let $$$i$$$ be the smallest such that numbers from $$$a_i$$$ to $$$a_n$$$ increase and $$$j$$$ be the smallest such that $$$a_j = a_i$$$.
Suppose that there is a sorting sequence that uses fewer operations than AmShZ strategy. Let's denote its first operation by $$$[l, r]$$$.
Consider several cases:
1. $$$r \geq i$$$. This means that we basically end up in string $$$S_{n-l}$$$. But we could have ended up in string $$$S_{n-j}$$$, which uses at most the same number of operations
2. $$$r \leq j$$$. Clearly, after operation $$$[l, r]$$$ $$$a_i$$$ can only decrease, so $$$j$$$ will still be the smallest index with $$$a_j = a_i$$$. By induction hypothesis, AmShZ strategy is optimal for resulting string, so the next operation in resulting string will be opertion $$$[j, i]$$$. But then we could have done $$$[j, i]$$$ first and then $$$[l, r]$$$.
3. $$$j \leq l$$$. As $$$r<i$$$, the smallest index $$$i$$$ such that $$$a_i \ldots$$$ $$$a_n$$$ are increasing hasn't changed. Numbers from $$$a_0$$$ to $$$a_j$$$ also haven't changed, so $$$j$$$ remains the same. So the next move according to AmShZ strategy will be operation $$$[j, i]$$$, so operation $$$[l, r]$$$ was useless
4. Last case. $$$l<j<r<i$$$. Note that all numbers up to $$$a_r$$$ will be strictly smallest then $$$a_i$$$ now. So we will have some new smallest $$$j1>r$$$ such that $$$a_j1 = a_i$$$. Then according to AmShZ strategy in the next move we will do operation $$$[j1, i]$$$.
But then we could instead do $$$[j1, i]$$$ first, and then $$$[l, r]$$$. But this is not optimal, as AmShZ strategy sorts $$$S_{n-j1}$$$ at least as fast as $$$S_{n - i}$$$.