The string t_1t_2 ... t_k is good if each letter of this string belongs to at least one palindrome of length greater than 1.

A palindrome is a string that reads the same backward as forward. For example, the strings A, BAB, ABBA, BAABBBAAB are palindromes, but the strings AB, ABBBAA, BBBA are not.

Here are some examples of good strings: 

  * t = AABBB (letters t_1, t_2 belong to palindrome t_1 ... t_2 and letters t_3, t_4, t_5 belong to palindrome t_3 ... t_5); 
  * t = ABAA (letters t_1, t_2, t_3 belong to palindrome t_1 ... t_3 and letter t_4 belongs to palindrome t_3 ... t_4); 
  * t = AAAAA (all letters belong to palindrome t_1 ... t_5); 



You are given a string s of length n, consisting of only letters A and B.

You have to calculate the number of good substrings of string s.

Input

The first line contains one integer n (1 ≤ n ≤ 3 ⋅ 10^5) — the length of the string s.

The second line contains the string s, consisting of letters A and B.

Output

Print one integer — the number of good substrings of string s.

Examples

Input


5
AABBB


Output


6


Input


3
AAA


Output


3


Input


7
AAABABB


Output


15

Note

In the first test case there are six good substrings: s_1 ... s_2, s_1 ... s_4, s_1 ... s_5, s_3 ... s_4, s_3 ... s_5 and s_4 ... s_5.

In the second test case there are three good substrings: s_1 ... s_2, s_1 ... s_3 and s_2 ... s_3.
import java.math.*;
import java.io.*;
import java.util.*;
import java.awt.*;


public class CP {
    public static void main(String[] args) throws Exception {
        /*new Thread(null, new Runnable() {
            @Override
            public void run() {
                try {
                    new Solver().solve();
                } catch (Exception e) {
                    e.printStackTrace();
                }
            }
        }, "Solver", 1l << 30).start();*/

        new Solver().solve();
    }
}

class Solver {
    final Helper hp;
    final int MAXN = 1000_006;
    final long MOD = (long) 1e9 + 7;

    Solver() {
        hp = new Helper(MOD, MAXN);
        hp.initIO(System.in, System.out);
    }


    void solve() throws Exception {
        int i, j, k;

        int N = hp.nextInt();
        String S = hp.next();
        BitSet bs = new BitSet();
        long[] A = new long[N + 7];

        for (i = 0; i < N; ++i) {
            bs.set(i, S.charAt(i) == 'A');
            if (bs.get(i)) A[i] = 1;
        }

        bs.set(N + 7 - 1); A[N + 7 - 1] = 1;
        SegmentTree segT = new SegmentTree(A);

        long ans = 0;
        int z = -7, o = -7;
        long l;
        for (i = 0; i < N; ++i) {
            if (bs.get(i)) {
                o = Math.max(o, i);
                while (o < N && bs.get(o)) ++o;
                l = o - i;
            } else {
                z = Math.max(z, i);
                while (z < N && !bs.get(z)) ++z;
                l = z - i;
            }

            ans += l - 1;
            //System.out.println(i + " = " + l);

            int p;

            if (bs.get(i)) {
                p = bs.nextClearBit(i);
                if (p < N) {
                    p = Math.min(bs.nextSetBit(p + 1), bs.nextClearBit(p + 1));
                }
                if (p < N && countO(segT, i, p) < 2) p = bs.nextSetBit(p + 1);
            } else {
                p = bs.nextSetBit(i);
                if (p >= 0 && p < N) {
                    p = Math.min(bs.nextSetBit(p + 1), bs.nextClearBit(p + 1));
                }
                if (p >= 0 && p < N && countZ(segT, i, p) < 2) p = bs.nextClearBit(p + 1);
            }

            if (p >= 0 && p < N) {
                ans += N - 1 - p + 1;
                //System.out.println(i + " -> " + p + " = " + ans);
            }
        }

        hp.println(ans);
        hp.flush();

        /*long ans = 0;
        for (i = 0; i < N; ++i) {
            for (j = i + 1; j < N; ++j) {
                if (isPalin(bs.get(i, j + 1), j - i + 1)) ++ans;
            }
        }
        System.out.println(ans);*/

    }

    boolean isPalin(BitSet bs, int l) {
        int c = bs.cardinality();
        return c == l || c == 0 || (c >= 2 && c <= l - 2);
    }

    long countO(SegmentTree s, int l, int r) {
        return s.rangeQuery(l, r, -7);
    }

    long countZ(SegmentTree s, int l, int r) {
        return r - l + 1 - s.rangeQuery(l, r, -7);
    }
}
class SegmentTree {
    private int N;
    private long[] tree, lazy;

    public SegmentTree(long[] ar) {
        N = 1;
        while (N < ar.length) N <<= 1;
        tree = new long[N * 2 - 1];
        lazy = new long[N * 2 - 1];

        for (int i = 0; i < ar.length; ++i) tree[i + N - 1] = ar[i];
        for (int i = N - 2; i >= 0; --i) tree[i] = tree[i * 2 + 1] + tree[i * 2 + 2];
    }

    public void pushDown(int i, int l, int r) {
        tree[i] += lazy[i] * (r - l + 1);
        if (i * 2 + 1 < tree.length) {
            lazy[i * 2 + 1] += lazy[i];
            lazy[i * 2 + 2] += lazy[i];
        }
        lazy[i] = 0;
    }

    public void pointUpdate(int i, long val) {
        i += N - 1;
        while (i >= 0) {
            tree[i] += val;
            i = i - 1 >> 1;
        }
    }

    public void rangeUpdate(int l, int r, long val) {
        update(0, 0, N - 1, l, r, val);
    }

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


    private void update(int i, int l, int r, int ql, int qr, long val) {
        pushDown(i, l, r);
        int mid = l + r >> 1, i2 = i << 1;
        if (l > qr || r < ql) return;
        else if (l >= ql && r <= qr) {
            lazy[i] += val;
            pushDown(i, l, r);
        } else {
            update(i2 + 1, l, mid, ql, qr, val);
            update(i2 + 2, mid + 1, r, ql, qr, val);

            // Rebuild tree[i] if necessary
            // tree[i] = tree[i2 + 1] + tree[i2 + 2];
        }
    }

    private long query(int i, int l, int r, int ql, int qr, long key) {
        pushDown(i, l, r);
        int mid = l + r >> 1, i2 = i << 1;
        if (l > qr || r < ql) return 0;
        else if (l >= ql && r <= qr) return tree[i];
        else {
            return query(i2 + 1, l, mid, ql, qr, key)
                    + query(i2 + 2, mid + 1, r, ql, qr, key);
        }
    }
}


class Helper {
    final long MOD;
    final int MAXN;

    public Helper(long mod, int maxn) {
        MOD = mod;
        MAXN = maxn;
    }


    public static int[] sieve;
    public static ArrayList<Integer> primes;

    public void setSieve() {
        primes = new ArrayList<>();
        sieve = new int[MAXN];
        int i, j;
        for (i = 2; i < MAXN; ++i)
            if (sieve[i] == 0) {
                primes.add(i);
                for (j = i; j < MAXN; j += i) {
                    sieve[j] = i;
                }
            }
    }


    public static long[] factorial;

    public void setFactorial() {
        factorial = new long[MAXN];
        factorial[0] = 1;
        for (int i = 1; i < MAXN; ++i) factorial[i] = factorial[i - 1] * i % MOD;
    }

    public long getFact(int n) {
        if (factorial == null) setFactorial();
        return factorial[n];
    }

    public long ncr(int n, int r) {
        if (r > n) return 0;
        if (factorial == null) setFactorial();
        long numerator = factorial[n];
        long denominator = factorial[r] * factorial[n - r] % MOD;
        return numerator * pow(denominator, MOD - 2, MOD) % MOD;
    }


    public long[] getLongArray(int size) throws Exception {
        long[] ar = new long[size];
        for (int i = 0; i < size; ++i) ar[i] = nextLong();
        return ar;
    }

    public int[] getIntArray(int size) throws Exception {
        int[] ar = new int[size];
        for (int i = 0; i < size; ++i) ar[i] = nextInt();
        return ar;
    }

    public String[] getStringArray(int size) throws Exception {
        String[] ar = new String[size];
        for (int i = 0; i < size; ++i) ar[i] = next();
        return ar;
    }

    public String joinElements(long[] ar) {
        StringBuilder sb = new StringBuilder();
        for (long itr : ar) sb.append(itr).append(" ");
        return sb.toString().trim();
    }


    public String joinElements(int[] ar) {
        StringBuilder sb = new StringBuilder();
        for (int itr : ar) sb.append(itr).append(" ");
        return sb.toString().trim();
    }

    public String joinElements(String[] ar) {
        StringBuilder sb = new StringBuilder();
        for (String itr : ar) sb.append(itr).append(" ");
        return sb.toString().trim();
    }

    public String joinElements(Object[] ar) {
        StringBuilder sb = new StringBuilder();
        for (Object itr : ar) sb.append(itr).append(" ");
        return sb.toString().trim();
    }


    public long gcd(long a, long b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    public int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }


    public long max(long[] ar) {
        long ret = ar[0];
        for (long itr : ar) ret = Math.max(ret, itr);
        return ret;
    }

    public int max(int[] ar) {
        int ret = ar[0];
        for (int itr : ar) ret = Math.max(ret, itr);
        return ret;
    }

    public long min(long[] ar) {
        long ret = ar[0];
        for (long itr : ar) ret = Math.min(ret, itr);
        return ret;
    }

    public int min(int[] ar) {
        int ret = ar[0];
        for (int itr : ar) ret = Math.min(ret, itr);
        return ret;
    }


    public long sum(long[] ar) {
        long sum = 0;
        for (long itr : ar) sum += itr;
        return sum;
    }

    public long sum(int[] ar) {
        long sum = 0;
        for (int itr : ar) sum += itr;
        return sum;
    }


    public long pow(long base, long exp, long MOD) {
        base %= MOD;
        long ret = 1;
        while (exp > 0) {
            if ((exp & 1) == 1) ret = ret * base % MOD;
            base = base * base % MOD;
            exp >>= 1;
        }
        return ret;
    }


    static byte[] buf = new byte[2048];
    static int index, total;
    static InputStream in;
    static BufferedWriter bw;


    public void initIO(InputStream is, OutputStream os) {
        try {
            in = is;
            bw = new BufferedWriter(new OutputStreamWriter(os));
        } catch (Exception e) {
        }
    }

    public void initIO(String inputFile, String outputFile) {
        try {
            in = new FileInputStream(inputFile);
            bw = new BufferedWriter(new OutputStreamWriter(
                    new FileOutputStream(outputFile)));
        } catch (Exception e) {
        }
    }

    private int scan() throws Exception {
        if (index >= total) {
            index = 0;
            total = in.read(buf);
            if (total <= 0)
                return -1;
        }
        return buf[index++];
    }

    public String next() throws Exception {
        int c;
        for (c = scan(); c <= 32; c = scan()) ;
        StringBuilder sb = new StringBuilder();
        for (; c > 32; c = scan())
            sb.append((char) c);
        return sb.toString();
    }

    public int nextInt() throws Exception {
        int c, val = 0;
        for (c = scan(); c <= 32; c = scan()) ;
        boolean neg = c == '-';
        if (c == '-' || c == '+')
            c = scan();
        for (; c >= '0' && c <= '9'; c = scan())
            val = (val << 3) + (val << 1) + (c & 15);
        return neg ? -val : val;
    }

    public long nextLong() throws Exception {
        int c;
        long val = 0;
        for (c = scan(); c <= 32; c = scan()) ;
        boolean neg = c == '-';
        if (c == '-' || c == '+')
            c = scan();
        for (; c >= '0' && c <= '9'; c = scan())
            val = (val << 3) + (val << 1) + (c & 15);
        return neg ? -val : val;
    }

    public void print(Object a) throws Exception {
        bw.write(a.toString());
    }

    public void printsp(Object a) throws Exception {
        print(a);
        print(" ");
    }

    public void println() throws Exception {
        bw.write("\n");
    }

    public void println(Object a) throws Exception {
        print(a);
        println();
    }

    public void flush() throws Exception {
        bw.flush();
    }
}
