This solution uses queue and deque. The primary concept is that starting from the last '1', we take all the zeroes that are before the previous '1'. If the previous digit is '1', then we take the last '0' that is available. If we have no '0's left, we take the first '1' that is available to us. To implement this process, we can store the indices of '0's in a queue and the indices of '1's in a deque. The time complexity is O(n).

Code(C++): ~~~~~ //All include & defs start

include <bits/stdc++.h>

using namespace std;

define ll long long

define pb push_back

define dd double

define ff float

define ss string

define ins insert

define vv vector

//All include and defs end

//Function to solve problem starts ll solve(ss s, ll n){ queue q; deque dq; for(ll i = n — 1; i >= 0; i --){ if(s[i] == '0'){ q.push(i); } else{ dq.pb(i); } } ll ans = 0; for(ll i = n — 1; i >= 0; i --){ if(s[i] == '1'){ if(! dq.empty()) dq.pop_front(); if(! q.empty()){ ans += (i + 1); q.pop(); while(q.front() > dq.front() && ! q.empty()){ q.pop(); } } else{ if(! dq.empty()){ ans += (i + 1); dq.pop_back(); } } } } ll total = (n * (n + 1)) / 2; return total — ans; }

//Function to solve problem ends

//main function starts

int main(){ ll t; cin >> t; while(t --){ ll n; cin >> n; ss s; cin >> s; cout << solve(s, n) << endl; } return 0; }

//main function ends ~~~~~