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.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author lucasr
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		MyScanner in = new MyScanner(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		FFruitSequences solver = new FFruitSequences();
		solver.solve(1, in, out);
		out.close();
	}

	static class FFruitSequences {
		static final int MIN = 1;
		int n;
		boolean[] ok;

		public void solve(int testNumber, MyScanner sc, PrintWriter out) {
			n = sc.nextInt();
			char[] vals = sc.next().toCharArray();
			ok = new boolean[n];
			for (int i = 0; i < n; i++) {
				ok[i] = vals[i] == '1';
			}
			out.println(getFreqs(0, n));
		}

		long simple(int from, int to) {
			long ans = 0;
			for (int i = from; i < to; i++) {
				int cur = 0, max = 0;
				for (int j = i + 1; j <= to; j++) {
					if (ok[j - 1]) {
						cur++;
						max = Math.max(max, cur);
					} else {
						cur = 0;
					}
					ans += max;
				}
			}
			return ans;
		}

		long getFreqs(int from, int to) {
			if (to - from <= MIN) {
				return simple(from, to);
			}
			long ans = 0;
			int med = (from + to) / 2;
			ans += getFreqs(from, med);
			ans += getFreqs(med, to);
			int maxBeg = 0, maxEnd = 0;
			for (int i = med; i < to; i++) {
				if (ok[i]) maxBeg++;
				else break;
			}
			for (int i = med - 1; i >= from; i--) {
				if (ok[i]) maxEnd++;
				else break;
			}
			long[] fRight = freqsFrom(med, to);
			long[] fLeft = freqsTo(from, med);
			long rSum = (maxBeg * (long) (maxBeg + 1)) / 2;
			long lSum = (maxEnd * (long) (maxEnd + 1)) / 2;
			ans -= rSum * maxEnd + maxBeg * lSum;
			for (int i = 0; i < fRight.length; i++) {
				long ff = Math.max(i, Math.min(i + 1, maxBeg + 1));
				long tt = Math.max(i, Math.min(i + maxEnd, maxBeg + maxEnd));
				ans += fRight[i] * getSum(ff, tt, maxEnd);
			}
			for (int i = 0; i < fLeft.length; i++) {
				long ff = Math.max(i, Math.min(i + 1, maxEnd + 1));
				long tt = Math.max(i, Math.min(i + maxBeg, maxEnd + maxBeg));
				ans += fLeft[i] * getSum(ff, tt, maxBeg);
			}
			for (int i = 1; i <= maxBeg; i++) {
				fRight[i]--;
			}
			for (int i = 1; i <= maxEnd; i++) {
				fLeft[i]--;
			}
			long[] acumR = acum(fRight);
			long[] acumL = acum(fLeft);
			for (int i = 0; i < Math.max(fLeft.length, fRight.length); i++) {
				long real = Math.max(i, maxBeg + maxEnd);
				long tmp = getM(acumR, i) * get(fLeft, i) + getM(acumL, i) * get(fRight, i);
				tmp -= get(fRight, i) * get(fLeft, i);
				tmp *= real;
				ans += tmp;
			}
			return ans;
		}

		long get(long[] arr, int index) {
			return index < arr.length ? arr[index] : 0;
		}

		long getM(long[] arr, int index) {
			return index < arr.length ? arr[index] : arr[arr.length - 1];
		}

		long[] acum(long[] tmp) {
			long[] ret = new long[tmp.length];
			ret[0] = tmp[0];
			for (int i = 1; i < tmp.length; i++) {
				ret[i] = ret[i - 1] + tmp[i];
			}
			return ret;
		}

		long getSum(long from, long to, long cant) {
			long tmp1 = (to * (to + 1)) / 2;
			long tmp2 = (from * (from - 1)) / 2;
			long ans = tmp1 - tmp2;
			long got = to - from + 1;
			cant -= got;
			ans += from * cant;
			return ans;
		}

		int getMax(int from, int to) {
			int cur = 0, max = 0;
			for (int i = from; i < to; i++) {
				if (ok[i]) {
					cur++;
					max = Math.max(max, cur);
				} else {
					cur = 0;
				}
			}
			return max;
		}

		long[] freqsFrom(int from, int to) {
			long[] ret = new long[getMax(from, to) + 1];

			int cur = 0, max = 0;
			for (int i = from; i < to; i++) {
				if (ok[i]) {
					cur++;
					max = Math.max(max, cur);
				} else {
					cur = 0;
				}
				ret[max]++;
			}
			return ret;
		}

		long[] freqsTo(int from, int to) {
			long[] ret = new long[getMax(from, to) + 1];

			int cur = 0, max = 0;
			for (int i = to - 1; i >= from; i--) {
				if (ok[i]) {
					cur++;
					max = Math.max(max, cur);
				} else {
					cur = 0;
				}
				ret[max]++;
			}
			return ret;
		}

	}

	static class MyScanner {
		private BufferedReader br;
		private StringTokenizer tokenizer;

		public MyScanner(InputStream is) {
			br = new BufferedReader(new InputStreamReader(is));
		}

		public String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}

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

	}
}

