rt

#include <bits/stdc++.h>
#include <map>

using namespace std;

const int MAXN = 2e6 + 5;
const int MAXlN = 8002;

int n;
string s;

struct Node {
	char a[MAXlN];
	int cnt;
} a[MAXlN];

char stk[MAXN];

bool check(int l, int r) {
	++r;
	if (a[l].cnt != a[r].cnt) return 0;
	for (int i = 0; i <= a[l].cnt; ++i) {
		if (a[l].a[i] != a[r].a[i]) return 0;
	}
	return 1;
}

int main() {
	// freopen("game.in", "r", stdin);
	// freopen("game.out", "w", stdout);
	ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> s;
	if (n <= 8000) {
//	if (0) {
		int ans = 0;
		a[0].cnt = -1;
		a[1].cnt = -1;
		for (int i = 1; i <= n; ++i) {
			if (i > 0) {
				a[i].cnt = a[i - 1].cnt;
				for (int j = 0; j <= a[i].cnt; ++j) {
					a[i].a[j] = a[i - 1].a[j];
				}
			}
			if (a[i].cnt > -1 && a[i].a[a[i].cnt] == s[i - 1]) {
				--a[i].cnt;
			} else {
				a[i].a[++a[i].cnt] = s[i - 1];
			}
		}
		a[n + 1].cnt = a[n].cnt;
		for (int i = 0; i <= a[n].cnt; ++i) {
			a[n + 1].a[i] = a[n].a[i];
		}
		
		for (int l = 0; l < n; ++l) {
			for (int r = l + 1; r < n; ++r) {
				if (check(l, r)) {
					++ans;
				}
			}
		}
		cout << ans;
	} else {
		long long ans = 0;
		map<__uint128_t, int> f;
		int cnt = -1;
		__uint128_t sum = 0;
		pair<__uint128_t, int> p;
		p.first = 0, p.second = 1;
		f.insert(p);
		for (int i = 0; i < n; ++i) {
			if (cnt > -1 && stk[cnt] == s[i]) {
				--cnt;
				sum /= 27;
			} else {
				stk[++cnt] = s[i];
				sum = sum * 27 + (s[i] - 'a' + 1);
			}
			if (f.find(sum) != f.end()) {
				ans += f[sum];
				++f[sum];
			} else {
				p.first = sum, p.second = 1;
				f.insert(p);
			}
		}
		cout << ans;
	}
	
	return 0;
}