#include "hiccup.h"
#define pii pair<int, int>
#define x first
#define y second
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
int n, lvl[N];
string str;
bool checkFunction(int mid) {
int cnt = 0;
stack<pii> stk;
for(int i = 0; i < n; ++i) {
if(str[i] == 'C') {
cnt--;
if(!stk.empty() && stk.top().y > cnt) return false;
stk.emplace(0, cnt);
}
if(str[i] == '!') {
if(stk.empty()) continue;
pii now = stk.top(); stk.pop();
if(++now.x == mid) continue;
stk.emplace(now);
}
if(str[i] == 'H') {
cnt++;
}
}
return stk.empty();
}
int HicCup(string S) {
str = S;
n = S.size();
int cnt = 0, pv = -1;
for(int i = 0; i < n; ++i) {
if(S[i] == 'H') cnt++, pv = -1;
if(S[i] == 'C') {
lvl[i] = cnt;
if(!~--cnt) return -1;
else pv = i;
}
if(S[i] == '!') {
if(pv == -1) return -1;
else lvl[i] = lvl[pv];
}
}
if(cnt) return -1;
int l = 0, r = S.size();
while(l < r) {
int mid = (l + r + 1) >> 1;
if(checkFunction(mid)) l = mid;
else r = mid-1;
}
return l;
}
