#include "hiccup.h"
#include <iostream>
#include <iomanip>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;
#define pb push_back
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL)
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
const int N = 1e5 + 10;
bool test(string s, int mid);
int HicCup(std::string s) {
int n = s.length();
int lo = 0, hi = n;
while (lo <= hi) {
int mid = (lo + hi) / 2;
// vector<int> suff(n + 2, 0);
// vector<int> pos(n + 2), del(n + 2, 0);
// for (int i = 0; i <= n; ++i) {
// pos[i] = i + 1;
// }
// pos[n + 1] = n + 1;
// for (int i = n; i >= 1; --i) {
// if (s[i] == '!') {
// suff[i] = 1 + suff[pos[i]];
// } else if (s[i] == 'H') {
// int p1 = pos[i];
// while (p1 <= n and del[p1] == true) {
// p1 = pos[p1];
// }
// int p2 = pos[p1];
// if (s[p1] == 'C' and suff[p2] >= mid) {
// int nxt = p2;
// for (int j = 0; j < mid + 1; ++j) {
// nxt = pos[p2];
// }
// while (nxt <= n and s[nxt] == '!' and !del[nxt]) {
// del[nxt] = true;
// nxt = pos[nxt];
// }
// pos[i - 1] = nxt;
// }
// }
// }
// bool ok = true;
// for (int i = 0; i <= n; i = pos[i]) {
// if (s[i] != '!') {
// ok = false;
// break;
// }
// }
if (test(s, mid)) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return lo - 1;
}
bool test(string s, int mid) {
int n = s.length();
stack<char> stk;
stk.push('#');
bool first = true;
for (int i = n - 1; i >= 0; --i) {
if (s[i] == 'H') {
while (!first and stk.top() == '!') {
stk.pop();
}
first = false;
if (stk.top() != 'C') {
return false;
}
stk.pop();
for (int j = 0; j < mid; ++j) {
if (stk.top() != '!') {
return false;
}
stk.pop();
}
} else {
stk.push(s[i]);
}
}
while (!first and stk.top() == '!') {
stk.pop();
}
return stk.top() == '#';
}
