#define _CRT_SECURE_NO_WARNINGS
#pragma GCC target("avx2")
#pragma GCC optimize("Ofast")
#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <iomanip>
#include <vector>
#include <set>
#include <map>

using namespace std;
const int N = 1e6 + 7, M = 1e9 + 7;

struct Jump {
    int l, r;
};

int n, l, r;
string s;

Jump jumps[N], obn[N];

char fst, sec;
int fstc, secc, PREF[N][26];

int get(int c, int l, int r) {
    if (l == 0) {
        return PREF[r][c];
    }
    return PREF[r][c] - PREF[l - 1][c];
}

bool good(int l, int r) {
    int cnt = 0;
    if (l == 0) {
        for (int c = 0; c < 26; c++) {
            if (PREF[r][c]) {
                cnt++;
            }
        }
    }
    else {
        for (int c = 0; c < 26; c++) {
            if (PREF[r][c] - PREF[l - 1][c]) {
                cnt++;
            }
        }
    }
    return cnt == 2;
}

bool vis[N];
void dfs(int v) {
    vis[v] = 1;
    if (jumps[v].l == -1) {
        return;
    }
    for (int i = jumps[v].l + 1; i <= jumps[v].r + 1; i++) {
        if (!vis[i]) {
            dfs(i);
        }
    }
}

int dp[N];

void prepare() {
    n = s.size();
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 26; j++) {
            PREF[i][j] = 0;
        }
    }
    for (int i = 0; i < n; i++) {
        PREF[i][s[i] - 'a']++;
        if (i != 0) {
            for (int j = 0; j < 26; j++) {
                PREF[i][j] += PREF[i - 1][j];
            }
        }
    }
    for (int i = 0; i < n; i++) {
        if (i == 0) {
            fst = s[i];
            fstc = 0;
            int j = i;
            while (j != n && s[j] == fst) {
                j++;
                fstc++;
            }
            if (j == n) {
                cout << "chastniy sluchay - " << s << "\n";
                return;
            }
            jumps[i].l = j;
            sec = s[j];
            secc = 0;
            while (j != n && (s[j] == sec || s[j] == fst)) {
                j++;
                if (s[j] == fst) {
                    fstc++;
                }
                else {
                    secc++;
                }
            }
            jumps[i].r = j - 1;
            l = jumps[i].l;
            r = jumps[i].r;
        }
        else {
            if (s[i - 1] == fst) {
                fstc--;
            }
            else {
                secc--;
            }
            if (i == 6) {
                cout << "";
            }
            if (!good(i, l)) {
                l++;
                while (!good(i, l) && l < n) {
                    l++;
                }
                if (l >= n) {
                    jumps[i].r = -1;
                    jumps[i].l = -1;
                }
                else {
                    jumps[i].l = l;
                    r = max(r, l);
                    while (good(i, r) && r < n) {
                        r++;
                    }
                    r--;
                    jumps[i].r = r;
                }
                continue;
            }
            jumps[i].l = l;
            jumps[i].r = r;
        }
    }
    jumps[n] = { -1,-1 };
}

long long stupid_solve() {
    long long ANS = 0;
    for (int i = 0; i < n; i++) {
        if (jumps[i].l == -1) {
            continue;
        }
        for (int j = i; j <= n; j++) {
            vis[j] = 0;
        }
        for (int j = jumps[i].l + 1; j <= jumps[i].r + 1; j++) {
            dfs(j);
        }
        for (int j = i; j <= n; j++) {
            if (vis[j]) {
                ANS++;
            }
        }
    }
        return ANS;
}

long long clever_solve() {
    long long ANS = 0;
        for (int i = 0; i <= n + 2; i++) {
            dp[i] = 0;
        }
        for (int i = 1; i < n; i++) {
            if (s[i] == s[i - 1]) {
                dp[i] = dp[i - 1];
            }
            else {
                if (i > 1 && good(i - 2, i)) {
                    dp[i] = i;
                }
                else {
                    if (i > 1) {
                        dp[i] = 1 + dp[i - 2];
                    }
                    else {
                        dp[i] = 1;
                    }
                }
            }
            ANS += dp[i];
        }
        return ANS;
}

string randomize() {
    int n = 200;
    string s;
    for (int i = 0; i < n; i++) {
        char c = 'a' + rand() % 26;
        if (s.size() != 0) {
            while (c == s[s.size() - 1]) {
                c = 'a' + rand() % 26;
            }
        }
        s.push_back('a' + rand() % 26);
    }
    return s;
}

signed main()
{
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    //freopen("trains.out", "w", stdout);
#else
    //freopen("sequence.in", "r", stdin);
    //freopen("sequence.out", "w", stdout);
#endif
    for (int I = 0; I < 20000; I++) {
        //s = randomize();
        cin >> s >> s;
        prepare();
        //long long S_ANS = stupid_solve();
        long long C_ANS = clever_solve();
        cout << C_ANS;
    }
}