Action Figures
Contest: Educational Codeforces Round 171 (Rated for Div. 2)
Difficulty rating: 1500
Tags: binary search, brute force, constructive algorithms, data structures, greedy, implementation

There is a shop that sells action figures near Monocarp's house. A new set of action figures will be released shortly; this set contains $$$n$$$ figures, the $$$i$$$-th figure costs $$$i$$$ coins and is available for purchase from day $$$i$$$ to day $$$n$$$.

For each of the $$$n$$$ days, Monocarp knows whether he can visit the shop.

Every time Monocarp visits the shop, he can buy any number of action figures which are sold in the shop (of course, he cannot buy an action figure that is not yet available for purchase). If Monocarp buys at least two figures during the same day, he gets a discount equal to the cost of the most expensive figure he buys (in other words, he gets the most expensive of the figures he buys for free).

Monocarp wants to buy exactly one $$$1$$$-st figure, one $$$2$$$-nd figure, ..., one $$$n$$$-th figure from the set. He cannot buy the same figure twice. What is the minimum amount of money he has to spend?

Input format:
The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

Each test case consists of two lines:

- the first line contains one integer $$$n$$$ ($$$1 \le n \le 4 \cdot 10^5$$$) — the number of figures in the set (and the number of days);
- the second line contains a string $$$s$$$ ($$$|s| = n$$$, each $$$s_i$$$ is either 0 or 1). If Monocarp can visit the shop on the $$$i$$$-th day, then $$$s_i$$$ is 1; otherwise, $$$s_i$$$ is 0.

Additional constraints on the input:

- in each test case, $$$s_n$$$ is 1, so Monocarp is always able to buy all figures during the $$$n$$$-th day;
- the sum of $$$n$$$ over all test cases does not exceed $$$4 \cdot 10^5$$$.

Output format:
For each test case, print one integer — the minimum amount of money Monocarp has to spend.

Constraints:
Time limit: 2.5 s
Memory limit: 512.0 MB

Note:
In the first test case, Monocarp buys the $$$1$$$-st figure on the $$$1$$$-st day and spends $$$1$$$ coin.

In the second test case, Monocarp can buy the $$$1$$$-st and the $$$3$$$-rd figure on the $$$3$$$-rd day, the $$$2$$$-nd and the $$$4$$$-th figure on the $$$4$$$-th day, and the $$$5$$$-th and the $$$6$$$-th figure on the $$$6$$$-th day. Then, he will spend $$$1+2+5=8$$$ coins.

In the third test case, Monocarp can buy the $$$2$$$-nd and the $$$3$$$-rd figure on the $$$3$$$-rd day, and all other figures on the $$$7$$$-th day. Then, he will spend $$$1+2+4+5+6 = 18$$$ coins.

Example input:
4
1
1
6
101101
7
1110001
5
11111

Example output:
1
8
18
6

Editorial:
Consider the following solution: we iterate on the number of figures we get for free (let this number be $$$k$$$), and for each value of $$$k$$$, we try to check if it is possible to get $$$k$$$ figures for free, and if it is, find the best figures which we get for free.
For a fixed value of $$$k$$$, it is optimal to visit the shop exactly $$$k$$$ times: if we visit the shop more than $$$k$$$ times, then during some visits, we buy only one figure — instead of that, we can buy figures from these visits during the last day, so there are no visits during which we buy only one figure.
It is quite obvious that if we want to visit the shop $$$k$$$ times, we always can do it during the last $$$k$$$ days with $$$s_i=1$$$. Let the last $$$k$$$ days with $$$s_i=1$$$ be $$$x_1, x_2, \dots, x_k$$$ (from right to left, so $$$x_1 > x_2 > \dots > x_k$$$). It is impossible to get a total discount of more than $$$(x_1 + x_2 + \dots + x_k)$$$ if we visit the shop only $$$k$$$ times, since when we visit the shop on day $$$i$$$, the maximum discount we can get during that day is $$$i$$$.
Now suppose we can't get the figures $$$\{x_1, x_2, \dots, x_k\}$$$ for free, but we can get some other set of figures $$$\{y_1, y_2, \dots, y_k\}$$$ ($$$y_1 > y_2 > \dots > y_k$$$) for free. Let's show that this is impossible. Consider the first $$$j$$$ such that $$$x_j \ne y_j$$$:
• if $$$y_j > x_j$$$, it means that on some suffix of days (from day $$$y_j$$$ to day $$$n$$$), we visit the shop $$$j$$$ times. But since $$$x_1, x_2, \dots, x_{j-1}, x_j$$$ are the last $$$j$$$ days when we visit the shop, then we can't visit the shop $$$j$$$ times from day $$$y_j$$$ to day $$$n$$$, so this is impossible;
• otherwise, if $$$y_j < x_j$$$, it means that during the day $$$x_j$$$, we get some figure $$$f$$$ for free, but it is not $$$x_j$$$. Let's get the figure $$$x_j$$$ for free during that day instead (swap the figures $$$f$$$ and $$$x_j$$$). Using a finite number of such transformations, we can show that we can get the figures $$$\{x_1, x_2, \dots, x_k\}$$$ for free.
Now, for a fixed value of $$$k$$$, we know which figures we should get for free. And if we increase the value of $$$k$$$, our total discount increases as well. Let's find the greatest possible $$$k$$$ with binary search, and we will get a solution working in $$$O(n \log n)$$$.
The only thing that's left is checking that some value of $$$k$$$ is achievable. To do it, we can mark the $$$k$$$ figures we try to get for free, and simulate the process, iterating the figures from left to right. If on some prefix, the number of figures we want to get for free is greater than the number of figures we pay for, then it is impossible, since we can't find a "match" for every figure we want to get for free.