Zookeeper is buying a carton of fruit to feed his pet wabbit. The fruits are a sequence of apples and oranges, which is represented by a binary string s_1s_2… s_n of length n. 1 represents an apple and 0 represents an orange.

Since wabbit is allergic to eating oranges, Zookeeper would like to find the longest contiguous sequence of apples. Let f(l,r) be the longest contiguous sequence of apples in the substring s_{l}s_{l+1}… s_{r}. 

Help Zookeeper find ∑_{l=1}^{n} ∑_{r=l}^{n} f(l,r), or the sum of f across all substrings.

Input

The first line contains a single integer n (1 ≤ n ≤ 5 ⋅ 10^5).

The next line contains a binary string s of length n (s_i ∈ \{0,1\}) 

Output

Print a single integer: ∑_{l=1}^{n} ∑_{r=l}^{n} f(l,r). 

Examples

Input


4
0110


Output


12


Input


7
1101001


Output


30


Input


12
011100011100


Output


156

Note

In the first test, there are ten substrings. The list of them (we let [l,r] be the substring s_l s_{l+1} … s_r):

  * [1,1]: 0 
  * [1,2]: 01 
  * [1,3]: 011 
  * [1,4]: 0110 
  * [2,2]: 1 
  * [2,3]: 11 
  * [2,4]: 110 
  * [3,3]: 1 
  * [3,4]: 10 
  * [4,4]: 0 



The lengths of the longest contiguous sequence of ones in each of these ten substrings are 0,1,2,2,1,2,2,1,1,0 respectively. Hence, the answer is 0+1+2+2+1+2+2+1+1+0 = 12.
#include <bits/stdc++.h>
#pragma GCC target( \
    "sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
#pragma comment(linker, "/STACK:167077260")
using namespace std;
const long double EPS = 0;
const long double EPS2 = 1e-12;
const long double PI = acos(-1);
int mod = (int)998244353;
const int MOD7 = 1000000007;
const int MOD9 = 1000000009;
const int a228 = 18;
const int inf = 1e9;
mt19937 rnd(time(0));
const long long kekmod = 1791791791;
const long long bestmod = 1148822869;
const int MAXN = 5e5 + 1;
long long n;
string s;
struct vt {
  long long sm, mn;
  vt(long long a, long long b) { sm = a, mn = b; }
  vt() { sm = mn = 0; }
};
vt t[4 * MAXN];
pair<long long, long long> add[4 * MAXN];
inline vt merge(vt a, vt b) { return {a.sm + b.sm, min(a.mn, b.mn)}; }
long long ans = 0;
vt pull(long long v, long long l, long long r) {
  if (add[v].first != -228) {
    vt ans = {(r - l) * add[v].first, add[v].first};
    return ans;
  }
  if (add[v].second) {
    vt ans = {t[v].sm + (r - l) * add[v].second, t[v].mn + add[v].second};
    return ans;
  }
  return t[v];
}
void push(long long v, long long l, long long r) {
  if (l != r - 1) {
    if (add[v].first > -228) {
      add[2 * v + 1].first = add[2 * v + 2].first = add[v].first;
      add[v].first = -228;
    }
    add[2 * v + 1].second += add[v].second,
        add[2 * v + 2].second += add[v].second;
    add[v].second = 0;
    t[v] =
        merge(pull(2 * v + 1, l, (l + r) / 2), pull(2 * v + 2, (l + r) / 2, r));
    return;
  }
  t[v] = pull(v, l, r);
  add[v] = {-228, 0};
}
void upd1(long long v, long long l, long long r, long long ql, long long qr,
          long long x) {
  if (l >= qr || ql >= r) return;
  push(v, l, r);
  if (l >= ql && r <= qr) {
    add[v].first = x;
    return;
  }
  upd1(2 * v + 1, l, (l + r) / 2, ql, qr, x);
  upd1(2 * v + 2, (l + r) / 2, r, ql, qr, x);
  t[v] =
      merge(pull(2 * v + 1, l, (l + r) / 2), pull(2 * v + 2, (l + r) / 2, r));
}
void upd2(long long v, long long l, long long r, long long ql, long long qr) {
  if (l >= qr || ql >= r) return;
  push(v, l, r);
  if (l >= ql && r <= qr) {
    add[v].second++;
    return;
  }
  upd2(2 * v + 1, l, (l + r) / 2, ql, qr);
  upd2(2 * v + 2, (l + r) / 2, r, ql, qr);
  t[v] =
      merge(pull(2 * v + 1, l, (l + r) / 2), pull(2 * v + 2, (l + r) / 2, r));
}
long long go(long long v, long long l, long long r, long long pf, long long x) {
  if (l >= pf) return -228;
  push(v, l, r);
  if (l == r - 1 && t[v].mn < x) return l;
  if (t[v].mn < x) {
    long long nw = go(2 * v + 1, l, (l + r) / 2, pf, x);
    if (nw == -228) nw = go(2 * v + 2, (l + r) / 2, r, pf, x);
    t[v] =
        merge(pull(2 * v + 1, l, (l + r) / 2), pull(2 * v + 2, (l + r) / 2, r));
    return nw;
  }
  return -228;
}
signed main() {
  ios_base::sync_with_stdio(0);
  cout.tie(0);
  cin.tie(0);
  srand(time(NULL));
  for (long long i = 0; i < 4 * MAXN; ++i) add[i] = {-228, 0};
  for (long long i = 0; i < 4 * MAXN; ++i) t[i] = {0, 0};
  cin >> n >> s;
  long long cnt = 0;
  for (long long i = 0; i < n; ++i) {
    if (s[i] == '0') {
      cnt = 0;
    } else {
      ++cnt;
      upd2(0, 0, n, i - cnt + 1, i + 1);
      long long rofl = go(0, 0, n, i - cnt + 1, cnt);
      if (rofl > -228) upd1(0, 0, n, rofl, i - cnt + 1, cnt);
    }
    ans += pull(0, 0, n).sm;
  }
  cout << ans;
}
