AC on #1, 2, 3, 4, 17

#include <bits/stdc++.h>
#define N 1000005

using std::string;

typedef long long LL;
typedef unsigned long long ull;
typedef string S;

LL n, d[N], l;
char t[N], tt[N];
S s;

inline void manacher() {
	LL r = 1, pos = 1;
	for (LL i = 1; i <= n; ++i) {
		d[i] = r < i ? 1 : std::min(d[(pos << 1) - i], r - i);
		while (t[i + d[i]] == t[i - d[i]]) ++d[i];
		if (i + d[i] > r) r = i + d[i], pos = i;
		ans += d[i] >> 1;
	}
}

int main() {
	std::cin >> n >> s;
	s = " " + s;
	t[l++] = '@', t[l++] ='#';
	for (LL i = 1; i <= n; ++i) t[l++] = s[i], t[l++] = '#';
	manacher();
	std::cout << ans;
	return 0;
}