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 comment(linker, "/stack:512000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native")
#pragma GCC optimize("unroll-loops")
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
mt19937_64 gen(time(nullptr));
namespace {
struct custom_hash {
  static uint64_t splitmix64(uint64_t x) {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }
  size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM =
        chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x + FIXED_RANDOM);
  }
};
template <typename T, typename F>
using HashMap = unordered_map<T, F, custom_hash>;
template <typename T>
using HashSet = unordered_set<T, custom_hash>;
}  // namespace
ll mod = 1e9 + 7;
namespace {
ll mul(ll a, ll b) {
  ll val = a * b - (ll)((ld)a * b / mod) * mod;
  if (val < 0) val += mod;
  if (val >= mod) val -= mod;
  return val;
}
ll poww(ll a, ll b) {
  ll val = 1;
  a %= mod;
  while (b > 0) {
    if (b % 2) val = mul(a, val);
    a = mul(a, a);
    b >>= 1;
  }
  return val % mod;
}
ll inv(ll a) { return poww(a, mod - 2); }
ll gcd(ll a, ll b) { return (a == 0 ? b : gcd(b % a, a)); }
ll gcdex(ll a, ll b, ll& x, ll& y) {
  if (a == 0) {
    x = 0;
    y = 1;
    return b;
  }
  ll x1, y1;
  ll d = gcdex(b % a, a, x1, y1);
  x = y1 - (b / a) * x1;
  y = x1;
  return d;
}
ll inv_eu(ll a, ll m) {
  ll x, y;
  ll g = gcdex(a, m, x, y);
  if (g != 1)
    assert(0);
  else {
    x = (x % m + m) % m;
    return x;
  }
}
}  // namespace
ll const maxn = 5e5 + 5;
struct segtree {
  struct node {
    node(ll x) : val(x){};
    node() : val(0){};
    ll val = 0;
    ll lazy = 0;
    void apply(int tl, int tr, ll add) {
      val += add * (tr - tl + 1);
      lazy += add;
    }
  };
  void push(int u, int tl, int tr) {
    if (t[u].lazy != 0) {
      int tm = (tl + tr) / 2;
      t[u * 2].apply(tl, tm, t[u].lazy);
      t[u * 2 + 1].apply(tm + 1, tr, t[u].lazy);
      t[u].lazy = 0;
    }
  }
  node merge(const node& a, const node& b) const { return node(a.val + b.val); }
  node get(int u, int tl, int tr, int l, int r) {
    if (r < l || tl > r || tr < l) {
      return neutral;
    }
    if (l <= tl && tr <= r) {
      return t[u];
    } else {
      push(u, tl, tr);
      int tm = (tl + tr) / 2;
      return merge(get(u * 2, tl, tm, l, r), get(u * 2 + 1, tm + 1, tr, l, r));
    }
  }
  template <typename... M>
  void upd(int u, int tl, int tr, int l, int r, const M&... m) {
    if (r < l || tl > r || tr < l) {
      return;
    }
    if (l <= tl && tr <= r) {
      t[u].apply(tl, tr, m...);
    } else {
      push(u, tl, tr);
      int tm = (tl + tr) / 2;
      upd(u * 2, tl, tm, l, r, m...);
      upd(u * 2 + 1, tm + 1, tr, l, r, m...);
      t[u] = merge(t[u * 2], t[u * 2 + 1]);
    }
  }
  template <class T>
  void build(int u, int tl, int tr, vector<T>& v) {
    if (tl == tr) {
      node tmp(v[tl]);
      t[u] = tmp;
    } else {
      int tm = (tl + tr) / 2;
      build(u * 2, tl, tm, v);
      build(u * 2 + 1, tm + 1, tr, v);
      t[u] = merge(t[u * 2], t[u * 2 + 1]);
    }
  }
  void casual_build(int u, int tl, int tr) {
    if (tl == tr) {
      return;
    } else {
      int tm = (tl + tr) / 2;
      casual_build(u * 2, tl, tm);
      casual_build(u * 2 + 1, tm + 1, tr);
      t[u] = merge(t[u * 2], t[u * 2 + 1]);
    }
  }
  segtree(ll n) : n(n) {
    t.resize(4 * n);
    casual_build(1, 0, n - 1);
  }
  template <class T>
  segtree(vector<T>& v) : n(v.size()) {
    t.resize(4 * n);
    build(1, 0, n - 1, v);
  }
  node get(int l, int r) { return get(1, 0, n - 1, l, r); }
  template <typename... M>
  void upd(int l, int r, const M&... m) {
    upd(1, 0, n - 1, l, r, m...);
  }
  int n;
  vector<node> t;
  node neutral;
};
template <typename T>
struct sparse {
  vector<vector<T>> sp;
  vector<T> lg;
  int n, k;
  T f(T& x, T& y) { return max(x, y); }
  sparse(vector<T>& v) {
    n = v.size();
    lg.resize(n + 1);
    lg[1] = 0;
    for (int i = 2; i <= n; i++) lg[i] = lg[i / 2] + 1;
    k = lg[n];
    sp.resize(n);
    for (int i = 0; i < n; i++) {
      sp[i].resize(k + 1);
      sp[i][0] = v[i];
    }
    for (int j = 1; j <= k; j++) {
      for (int i = 0; i + (1 << j) <= n; i++) {
        sp[i][j] = f(sp[i][j - 1], sp[i + (1 << (j - 1))][j - 1]);
      }
    }
  }
  T get(int l, int r) {
    int j = lg[r - l + 1];
    return f(sp[l][j], sp[r - (1 << j) + 1][j]);
  }
};
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ll n;
  cin >> n;
  vector<ll> a(n);
  for (ll i = 0; i < n; i++) {
    char c;
    cin >> c;
    a[i] = (c == '1');
  }
  ll cur = 0;
  vector<ll> kek(n);
  for (ll i = n - 1; i >= 0; i--) {
    if (a[i] == 1)
      cur++;
    else
      cur = 0;
    kek[i] = cur;
  }
  sparse<ll> table(kek);
  segtree Tree(n);
  ll ans = 0;
  vector<ll> rofl = {-1};
  cur = 0;
  for (ll i = 0; i < n; i++) {
    if (a[i] == 0) {
      if (i > 0 and a[i - 1] == 1) rofl.push_back(i - 1);
      ll x = Tree.get(0, n - 1).val;
      ans += x;
      cur = 0;
      continue;
    }
    cur++;
    ll j = rofl.back();
    ll l = -1, r = j + 1;
    while (l < r - 1) {
      ll m = (l + r) / 2;
      if (table.get(m, j) < cur) {
        r = m;
      } else
        l = m;
    }
    if (l == -1)
      l = 0;
    else
      l += 2;
    Tree.upd(r, i, 1);
    ll x = Tree.get(0, n - 1).val;
    ans += x;
    ll tt = 0;
  }
  cout << ans << endl;
  return 0;
}
