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.
/**
 * author: derrick20
 * created: 10/17/20 9:47 PM
 */

import java.io.*;
import java.util.*;

public class FruitSequences implements Runnable {
    public static void main(String[] args) throws Exception {
        new Thread(null, new FruitSequences(), ": )", 1 << 28).start();
    }

    public void run() {
        FastScanner sc = new FastScanner();
        PrintWriter out = new PrintWriter(System.out);

        int N = sc.nextInt();
        char[] s = sc.next().toCharArray();
        int[] a = new int[N + 1];
        for (int i = 1; i <= N; i++)
            a[i] = s[i - 1] - '0';

        SegmentTree st = new SegmentTree(N);
        int streak = 0;
        long ans = 0;
        long contrib = 0;
        for (int r = 1; r <= N; r++) {
            if (a[r] == 1) {
//                int lo = 1;
//                int hi = r - 1;
//                while (lo < hi) {
//                    // 01
//                    // lowest so that max <= current streak
//                    int mid = (lo + hi) / 2;
//                    if (st.query(mid, r - 1) <= streak) {
//                        hi = mid;
//                    } else {
//                        lo = mid + 1;
//                    }
//                }
                int lo2 = st.search(streak);
//                System.out.println(lo + " " + lo2);
                // This is the number of intervals I CONTRIBUTE to
                int len = r - lo2 + 1;
                contrib += len;
                st.update(r - streak, r, 1);
                streak++;
            } else {
                streak = 0;
            }
//            System.out.println("Contrib at " + r + " = " + contrib);
            ans += contrib;
        }
        out.println(ans);
        out.close();
    }

    static class SegmentTree {
        int[] max;
        int[] delta;
        int N;
        public SegmentTree(int MAX) {
            N = MAX + 1;
            max = new int[4 * N];
            delta = new int[4 * N];
        }

        public int search(int k) {
            int node = 1;
            // find leftmost position so that max from [x, N - 1] is <= k
            // 221100
            int curr = 0;
            int sl = 0;
            int sr = N - 1;
            while (sl < sr) {
                pushDown(node);
                int right = max[2 * node + 1] + delta[2 * node + 1];
                int mid = (sl + sr) / 2;
                if (right > k) {
                    node = 2 * node + 1;
                    sl = mid + 1;
                } else {
                    // skip right
                    node = 2 * node;
                    sr = mid;
                    curr = Math.max(curr, right);
                }
            }
            // Actually, because of the nature of binary lifting, we go one
            // too far
            return sl + 1;
        }

        public void pushDown(int node) {
            delta[2 * node] += delta[node];
            delta[2 * node + 1] += delta[node];
            max[node] += delta[node];
            delta[node] = 0;
        }

        public int query(int l, int r) {
            return queryHelper(1, 0, N - 1, l, r);
        }

        public void pullUp(int node) {
            max[node] = Math.max(max[2 * node] + delta[2 * node], max[2 * node + 1] + delta[2 * node + 1]);
        }

        public int queryHelper(int node, int sl, int sr, int l, int r) {
            if (l <= sl && sr <= r) {
                return max[node] + delta[node];
            } else if (sr < l || r < sl) {
                return 0;
            } else {
                int mid = (sl + sr) / 2;
                pushDown(node);
                int left = queryHelper(2 * node, sl, mid, l, r);
                int right = queryHelper(2 * node + 1, mid + 1, sr, l, r);
                pullUp(node);
                return Math.max(left, right);
            }
        }

        public void update(int l, int r, int amt) {
            updateHelper(1, 0, N - 1, l, r, amt);
        }

        public void updateHelper(int node, int sl, int sr, int l, int r, int amt) {
            if (l <= sl && sr <= r) {
                delta[node] += amt;
            } else if (sr < l || r < sl) {
                return;
            } else {
                int mid = (sl + sr) / 2;
                pushDown(node);
                updateHelper(2 * node, sl, mid, l, r, amt);
                updateHelper(2 * node + 1, mid + 1, sr, l, r, amt);
                pullUp(node);
            }
        }
    }

    static class FastScanner {
        private int BS = 1 << 16;
        private char NC = (char) 0;
        private byte[] buf = new byte[BS];
        private int bId = 0, size = 0;
        private char c = NC;
        private double cnt = 1;
        private BufferedInputStream in;

        public FastScanner() {
            in = new BufferedInputStream(System.in, BS);
        }

        public FastScanner(String s) {
            try {
                in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
            } catch (Exception e) {
                in = new BufferedInputStream(System.in, BS);
            }
        }

        private char getChar() {
            while (bId == size) {
                try {
                    size = in.read(buf);
                } catch (Exception e) {
                    return NC;
                }
                if (size == -1) return NC;
                bId = 0;
            }
            return (char) buf[bId++];
        }

        public int nextInt() {
            return (int) nextLong();
        }

        public int[] nextInts(int N) {
            int[] res = new int[N];
            for (int i = 0; i < N; i++) {
                res[i] = (int) nextLong();
            }
            return res;
        }

        public long[] nextLongs(int N) {
            long[] res = new long[N];
            for (int i = 0; i < N; i++) {
                res[i] = nextLong();
            }
            return res;
        }

        public long nextLong() {
            cnt = 1;
            boolean neg = false;
            if (c == NC) c = getChar();
            for (; (c < '0' || c > '9'); c = getChar()) {
                if (c == '-') neg = true;
            }
            long res = 0;
            for (; c >= '0' && c <= '9'; c = getChar()) {
                res = (res << 3) + (res << 1) + c - '0';
                cnt *= 10;
            }
            return neg ? -res : res;
        }

        public double nextDouble() {
            double cur = nextLong();
            return c != '.' ? cur : cur + nextLong() / cnt;
        }

        public double[] nextDoubles(int N) {
            double[] res = new double[N];
            for (int i = 0; i < N; i++) {
                res[i] = nextDouble();
            }
            return res;
        }

        public String next() {
            StringBuilder res = new StringBuilder();
            while (c <= 32) c = getChar();
            while (c > 32) {
                res.append(c);
                c = getChar();
            }
            return res.toString();
        }

        public String nextLine() {
            StringBuilder res = new StringBuilder();
            while (c <= 32) c = getChar();
            while (c != '\n') {
                res.append(c);
                c = getChar();
            }
            return res.toString();
        }

        public boolean hasNext() {
            if (c > 32) return true;
            while (true) {
                c = getChar();
                if (c == NC) return false;
                else if (c > 32) return true;
            }
        }
    }

    static void ASSERT(boolean assertion, String message) {
        if (!assertion) throw new AssertionError(message);
    }
    static void ASSERT(boolean assertion) {
        if (!assertion) throw new AssertionError();
    }
}