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.
import java.util.*;
import java.io.*;
import java.math.*;
 
public class Main {
    static PrintWriter out;
    static Reader in;
    public static void main(String[] args) throws IOException {
        //out = new PrintWriter(new File("out.txt"));
        //PrintWriter out = new PrintWriter(System.out);
        //in = new Reader(new FileInputStream("in.txt"));
        //Reader in = new Reader();
        input_output();
        Main solver = new Main();
        solver.solve();
        out.flush();
        out.close();
 
    }
 
    static int INF = (int)1e9-1;
    static int maxn = (int)1e5+5;
    static int mod = 998_244_353;
    static int n, m, q, k, t;

    void solve() throws IOException{
    	n = in.nextInt();

    	String s = in.next();

        long[] pre = new long[n+1];
        pre[1] = 1;
        for (int i = 2; i <= n; i++) pre[i] = pre[i-1]+((long)i*(i+1))/2L;

    	TreeSet<Integer> left[] = new TreeSet[n+2],
    					 right[] = new TreeSet[n+2];
    	for (int i = 0; i <= n+1; i++) {
    		left[i] = new TreeSet<Integer>();
    		right[i] = new TreeSet<Integer>();
    	}

    	long ans = 0;
    	int cur = 0;
    	for (int i = 0; i < n; i++) {
    		if (s.charAt(i) == '1') {
    			cur++;
    			right[cur].add(i);
    		} else {
    			ans += pre[cur];
    			cur = 0;
    		}
    	}
    	ans += pre[cur];

        cur = 0;
    	for (int i = n-1; i >= 0; i--) {
    		if (s.charAt(i) == '1') {
    			cur++;
    			left[cur].add(i);
    		} else cur = 0;
    	}

    	for (int i = 0; i <= n+1; i++) {
    		left[i].add(-1);
    		right[i].add(n);
    	}



    	cur = 0;
    	int l = 0, r = 0;
    	for (int i = 0; i < n; i++) {
    		if (s.charAt(i) == '1') {
    			cur++;

                if (i-cur+1 == 0) continue;

    			l = left[cur+1].lower(i-cur+1);
    			if (i != n-1 && s.charAt(i+1) == '0') {
    				r = right[cur].higher(i);
    			} else r = i+1;

    			ans += (long)cur*(i-cur-l)*(r-i);
    		} else {
    			cur = 0;
    		}
    	}

    	cur = 0;
    	for (int i = n-1; i >= 0; i--) {
    		if (s.charAt(i) == '1') {
    			cur++;

    			r = right[cur].higher(i+cur-1);
    			//l = left[cur+1].lower(i); // remove
                l = i-1;

    			ans += (long)cur*(i-l)*(r-i-cur);
    		} else {
    			cur = 0;
    		}
    	}

    	out.println(ans);
    }

    //<>

    static class Reader {
 
        private InputStream mIs;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
    
        public Reader() {
            this(System.in);
        }
    
        public Reader(InputStream is) {
            mIs = is;
        }
    
        public int read() {
            if (numChars == -1) {
                throw new InputMismatchException();
    
        }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = mIs.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }
    
        public String nextLine() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isEndOfLine(c));
            return res.toString();
        }
    
        public String next() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }
    
        double nextDouble()
        {
            return Double.parseDouble(next());
        }
    
        public long nextLong() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }
    
        public int nextInt() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }
    
        public boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
    
        public boolean isEndOfLine(int c) {
            return c == '\n' || c == '\r' || c == -1;
        }
 
    }
    static void input_output() throws IOException {
        File f = new File("in.txt");
        if(f.exists() && !f.isDirectory()) { 
            in = new Reader(new FileInputStream("in.txt"));
        } else in = new Reader();
        f = new File("out.txt");
        if(f.exists() && !f.isDirectory()) {
            out = new PrintWriter(new File("out.txt"));
        } else out = new PrintWriter(System.out);
    }
}