/** @file 805.cpp @title No.805 UMG - yukicoder @url https://yukicoder.me/problems/no/805 **/ #include using namespace std; typedef long long LL; #define ALL(obj) (obj).begin(), (obj).end() #define REP(i, N) for (int i = 0; i < (N); ++i) int main() { int N; cin >> N; string S; cin >> S; vector m; vector dp_U(N + 1, 0); vector dp_G(N + 1, 0); REP(i, N) { if (S.substr(i, 1) == "M") { m.push_back(i); } if (S.substr(i, 1) == "U") { dp_U[i + 1] = dp_U[i] + 1; } else { dp_U[i + 1] = dp_U[i]; } if (S.substr(i, 1) == "G") { dp_G[i + 1] = dp_G[i] + 1; } else { dp_G[i + 1] = dp_G[i]; } } int M = (int)m.size(); LL ans = 0; if (M != 0) { REP(i, M) { int numU = dp_U[m[i]] - dp_U[0]; int numG = dp_G[N] - dp_G[m[i]]; if (numU <= numG) { for (int j = 0; j < m[i]; j++) { // cout << "j\t" << j << " S[j]:\t" << S[j] << "\n"; // cout << "m[i]+(m[i]-j)\t" << m[i] + (m[i] - j) << " S[]:\t" << S[j] << "\n"; if (S[j] == 'U' && S[m[i] + (m[i] - j)] == 'G') { ans++; } } } else { for (int j = m[i] + 1; j < N; j++) { // cout << "j\t" << j << " S[j]:\t" << S[j] << "\n"; // cout << "m[i]-(j-m[i])\t" << m[i] - (j - m[i]) << " S[]:\t" << S[m[i] - (j - m[i])] << "\n"; if (S[j] == 'G' && S[m[i] - (j - m[i])] == 'U') { ans++; } } } } } cout << ans << endl; return 0; }