First, consider the following \(\Theta(N^2)\)-time solution:

Initially, let \(S=(),\operatorname{ans}=0\). For \(i=1,2,\ldots,N\), do the following:

• Let \(S\leftarrow(s_j\barwedge A _ i) _ {j=1,2,\ldots,i-1}\mathbin{+\mkern-10mu+}A _ i\), where \(s _ j\) is the \(j\)-th element of \(S\), and \(\mathbin{+\mkern-10mu+}\) denotes the concatenation of sequences. Let \(\operatorname{ans}\leftarrow\operatorname{ans}+\sum _ {j=1} ^ {i} s_j\).

When the algorithm completes, \(\operatorname{ans}\) is the correct answer, but it does not finish in the execution time limit.

Here, we use the fact that \(S\) only contains the elements of \(\{0,1\}\). By managing the numbers of \(0\) and \(1\) in \(S\), the problem can be solved in a total of \(\Theta(N)\) time.

The sample codes follows.

N = int(input())
A = input()

zero, one = 0, 0
ans = 0

for a in A:
    if a == '0':
        zero, one = 1, zero + one
    else:
        zero, one = one, zero + 1
    ans += one

print(ans)

#include <vector>
#include <iostream>
#include <utility>

int main() {
    using namespace std;

    unsigned long N;
    cin >> N;
    vector<char> A(N);
    for (auto &&a : A)cin >> a;

    unsigned long ans{};

    using count_t = pair<unsigned long, unsigned long>;
    count_t counter{};
    auto&&[zero, one]{counter};

    for (const auto a : A) {
        counter = a == '1' ? count_t{one, zero + 1} : count_t{1, one + zero};
        ans += one;
    }

    cout << ans << endl;

    return 0;
}