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.*;

public class Main {
    public static void main(String args[]) {new Main().run();}

    FastReader in = new FastReader();
    PrintWriter out = new PrintWriter(System.out);
    void run(){
        work();
        out.flush();
    }
    long mod=998244353;
    long gcd(long a,long b) {
        return a==0?b:gcd(b%a,a);
    }
    void work() {
        int n=ni();
        int[] A=new int[n];
        String str=ns();
        for(int i=0;i<n;i++){
            A[i]=str.charAt(i)-'0';
        }
        Stack<int[]> lstack=new Stack<>();
        Stack<int[]> rstack=new Stack<>();
        int[] lrec=new int[n];
        int[] rrec=new int[n];
        long ret=0;
        long c=0;
        for(int i=0;i<n;i++){
            if(A[i]==0){
                c=0;
            }else{
                c++;
                while(lstack.size()>0&&lstack.peek()[1]<c){
                    lstack.pop();
                }
                if(lstack.size()==0){
                    ret+=(i-c+1)*c;
                    lrec[i]=0;
                }else{
                    int idx=lstack.peek()[0];
                    ret+=(i-c-(idx-c+1))*c;
                    lrec[i]=(int)(idx-c+2);
                }
                if(i+1<n&&A[i+1]==0){
                    lstack.add(new int[]{i,(int)c});
                }
            }
        }
        c=0;
        for(int i=n-1;i>=0;i--){
            if(A[i]==0){
                c=0;
            }else{
                c++;
                while(rstack.size()>0&&rstack.peek()[1]<=c){
                    rstack.pop();
                }
                if(rstack.size()==0){
                    ret+=(n-i-c)*c+c*(c+1)/2;
                    rrec[i]=n-1;
                }else{
                    int idx=rstack.peek()[0];
                    ret+=(idx+c-i-c)*c+c*(c+1)/2;
                    rrec[i]=(int)(idx+c-1);
                }
                if(i-1>=0&&A[i-1]==0){
                    rstack.add(new int[]{i,(int)c});
                }
            }
        }
        for(int i=0,j=0;i<n;i=j){
            if(A[i]==1){
                for(;j<n&&A[j]==1;j++);
                long r=rrec[i]-j+1;
                long l=i-lrec[j-1];
                ret+=r*l*(j-i);
            }else{
                j++;
            }
        }
        out.println(ret);
    }

    //input
    @SuppressWarnings("unused")
    private ArrayList<Integer>[] ng(int n, int m) {
        ArrayList<Integer>[] graph=(ArrayList<Integer>[])new ArrayList[n];
        for(int i=0;i<n;i++) {
            graph[i]=new ArrayList<>();
        }
        for(int i=1;i<=m;i++) {
            int s=in.nextInt()-1,e=in.nextInt()-1;
            graph[s].add(e);
            graph[e].add(s);
        }
        return graph;
    }

    private ArrayList<long[]>[] ngw(int n, int m) {
        ArrayList<long[]>[] graph=(ArrayList<long[]>[])new ArrayList[n];
        for(int i=0;i<n;i++) {
            graph[i]=new ArrayList<>();
        }
        for(int i=1;i<=m;i++) {
            long s=in.nextLong()-1,e=in.nextLong()-1,w=in.nextLong();
            graph[(int)s].add(new long[] {e,w});
//            graph[(int)e].add(new long[] {s,w});
        }
        return graph;
    }

    private int ni() {
        return in.nextInt();
    }

    private long nl() {
        return in.nextLong();
    }

    private String ns() {
        return in.next();
    }

    private long[] na(int n) {
        long[] A=new long[n];
        for(int i=0;i<n;i++) {
            A[i]=in.nextLong();
        }
        return A;
    }
    private int[] nia(int n) {
        int[] A=new int[n];
        for(int i=0;i<n;i++) {
            A[i]=in.nextInt();
        }
        return A;
    }
}

class FastReader
{
    BufferedReader br;
    StringTokenizer st;

    public FastReader()
    {
        br=new BufferedReader(new InputStreamReader(System.in));
    }


    public String next()
    {
        while(st==null || !st.hasMoreElements())//回车，空行情况
        {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }

    public int nextInt()
    {
        return Integer.parseInt(next());
    }

    public long nextLong()
    {
        return Long.parseLong(next());
    }
}