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.Iterator;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.io.InputStream;
import java.util.function.IntFunction;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) throws Exception {
        Thread thread = new Thread(null, new TaskAdapter(), "", 1 << 29);
        thread.start();
        thread.join();
    }

    static class TaskAdapter implements Runnable {
        @Override
        public void run() {
            InputStream inputStream = System.in;
            OutputStream outputStream = System.out;
            FastInput in = new FastInput(inputStream);
            PrintWriter out = new PrintWriter(outputStream);
            FFruitSequences solver = new FFruitSequences();
            solver.solve(1, in, out);
            out.close();
        }
    }

    static class FFruitSequences {
        public void solve(int testNumber, FastInput in, PrintWriter out) {
            int n = in.readInt();
            int[] seq = new int[n];
            for (int i = 0; i < n; i++) {
                seq[i] = in.readChar() - '0';
            }


            long extra = 0;
            List<Event> events = new ArrayList<>(n);
            for (int i = 0; i < n; i++) {
                if (seq[i] == 0) {
                    continue;
                }
                int j = i;
                while (j + 1 < n && seq[j + 1] == 1) {
                    j++;
                }
                if (j > i) {
                    int internal = j - i + 1 - 2;
                    for (int k = 1; k <= internal; k++) {
                        extra += (long) k * (internal - k + 1);
                    }
                }
                for (int k = i; k <= j; k++) {
                    events.add(new Event(i, k - i + 1, k, n - 1));
                }
                for (int k = j; k >= i; k--) {
                    events.add(new Event(k, j - k + 1, j, n - 1));
                }

                i = j;
            }
            events.sort((a, b) -> Integer.compare(a.l, b.l));
            Range2DequeAdapter<Event> dq = new Range2DequeAdapter<>(i -> events.get(i), 0, events.size() - 1);
            SegmentBeat sb = new SegmentBeat(0, n - 1, i -> 0);

            long sum = 0;
            for (int i = n - 1; i >= 0; i--) {
                while (!dq.isEmpty() && dq.peekLast().l >= i) {
                    Event event = dq.removeLast();
                    sb.updateMin(event.lo, event.hi, 0, n - 1, -event.profit);
                }
                long cnt = sb.querySum(i, n - 1, 0, n - 1);
                sum += cnt;
            }
            out.println(-sum + extra);
        }

    }

    static class Event {
        int l;
        int profit;
        int lo;
        int hi;

        public Event(int l, int profit, int lo, int hi) {
            this.l = l;
            this.profit = profit;
            this.lo = lo;
            this.hi = hi;
        }

    }

    static class SegmentBeat implements Cloneable {
        private SegmentBeat left;
        private SegmentBeat right;
        private long first;
        private long second;
        private int firstCnt;
        private static long inf = (long) 2e18;
        private long sum;

        private void setMin(long x) {
            if (first <= x) {
                return;
            }
            sum -= (first - x) * firstCnt;
            first = x;
        }

        public void pushUp() {
            first = Math.max(left.first, right.first);
            second = Math.max(left.first == first ? left.second : left.first, right.first == first ? right.second : right.first);
            firstCnt = (left.first == first ? left.firstCnt : 0) + (right.first == first ? right.firstCnt : 0);
            sum = left.sum + right.sum;
        }

        public void pushDown() {
            left.setMin(first);
            right.setMin(first);
        }

        public SegmentBeat(int l, int r, IntToLongFunction func) {
            if (l < r) {
                int m = DigitUtils.floorAverage(l, r);
                left = new SegmentBeat(l, m, func);
                right = new SegmentBeat(m + 1, r, func);
                pushUp();
            } else {
                sum = first = func.apply(l);
                second = -inf;
                firstCnt = 1;
            }
        }

        private boolean covered(int ll, int rr, int l, int r) {
            return ll <= l && rr >= r;
        }

        private boolean noIntersection(int ll, int rr, int l, int r) {
            return ll > r || rr < l;
        }

        public void updateMin(int ll, int rr, int l, int r, long x) {
            if (noIntersection(ll, rr, l, r)) {
                return;
            }
            if (covered(ll, rr, l, r)) {
                if (first <= x) {
                    return;
                }
                if (second < x) {
                    setMin(x);
                    return;
                }
            }
            pushDown();
            int m = DigitUtils.floorAverage(l, r);
            left.updateMin(ll, rr, l, m, x);
            right.updateMin(ll, rr, m + 1, r, x);
            pushUp();
        }

        public long querySum(int ll, int rr, int l, int r) {
            if (noIntersection(ll, rr, l, r)) {
                return 0;
            }
            if (covered(ll, rr, l, r)) {
                return sum;
            }
            pushDown();
            int m = DigitUtils.floorAverage(l, r);
            return left.querySum(ll, rr, l, m) +
                    right.querySum(ll, rr, m + 1, r);
        }

        private SegmentBeat deepClone() {
            SegmentBeat seg = clone();
            if (seg.left != null) {
                seg.left = seg.left.deepClone();
            }
            if (seg.right != null) {
                seg.right = seg.right.deepClone();
            }
            return seg;
        }

        protected SegmentBeat clone() {
            try {
                return (SegmentBeat) super.clone();
            } catch (CloneNotSupportedException e) {
                throw new RuntimeException(e);
            }
        }

        private void toString(StringBuilder builder) {
            if (left == null && right == null) {
                builder.append(sum).append(",");
                return;
            }
            pushDown();
            left.toString(builder);
            right.toString(builder);
        }

        public String toString() {
            StringBuilder builder = new StringBuilder();
            deepClone().toString(builder);
            if (builder.length() > 0) {
                builder.setLength(builder.length() - 1);
            }
            return builder.toString();
        }

    }

    static class DigitUtils {
        private DigitUtils() {
        }

        public static int floorAverage(int x, int y) {
            return (x & y) + ((x ^ y) >> 1);
        }

    }

    static interface SimplifiedStack<T> extends Iterable<T> {
    }

    static interface IntToLongFunction {
        long apply(int x);

    }

    static class Range2DequeAdapter<T> implements SimplifiedDeque<T> {
        IntFunction<T> data;
        int l;
        int r;

        public Range2DequeAdapter(IntFunction<T> data, int l, int r) {
            this.data = data;
            this.l = l;
            this.r = r;
        }

        public boolean isEmpty() {
            return l > r;
        }

        public T peekLast() {
            return data.apply(r);
        }

        public T removeLast() {
            return data.apply(r--);
        }

        public Iterator<T> iterator() {
            return new Iterator<T>() {
                int iter = l;


                public boolean hasNext() {
                    return iter <= r;
                }


                public T next() {
                    return data.apply(iter++);
                }
            };
        }

    }

    static class FastInput {
        private final InputStream is;
        private byte[] buf = new byte[1 << 13];
        private int bufLen;
        private int bufOffset;
        private int next;

        public FastInput(InputStream is) {
            this.is = is;
        }

        private int read() {
            while (bufLen == bufOffset) {
                bufOffset = 0;
                try {
                    bufLen = is.read(buf);
                } catch (IOException e) {
                    bufLen = -1;
                }
                if (bufLen == -1) {
                    return -1;
                }
            }
            return buf[bufOffset++];
        }

        public void skipBlank() {
            while (next >= 0 && next <= 32) {
                next = read();
            }
        }

        public int readInt() {
            int sign = 1;

            skipBlank();
            if (next == '+' || next == '-') {
                sign = next == '+' ? 1 : -1;
                next = read();
            }

            int val = 0;
            if (sign == 1) {
                while (next >= '0' && next <= '9') {
                    val = val * 10 + next - '0';
                    next = read();
                }
            } else {
                while (next >= '0' && next <= '9') {
                    val = val * 10 - next + '0';
                    next = read();
                }
            }

            return val;
        }

        public char readChar() {
            skipBlank();
            char c = (char) next;
            next = read();
            return c;
        }

    }

    static interface SimplifiedDeque<T> extends SimplifiedStack<T> {
    }
}

