#include "hiccup.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef pair <int, int> pii;
int HicCup(string s) {
int n = s.size();
int h = 0, hc = 0;
bool flag = false, flag2 = false;
for(int i = 0; i < n; i++) {
if(s[i] == 'H') {
flag2 = true;
h++;
flag = false;
}
if(s[i] == 'C') {
h--;
hc++;
flag = false;
flag2 = false;
}
if(s[i] == '!' && !flag) {
if(hc == 0) return -1;
if(flag2) return -1;
hc--;
flag = true;
}
if(h < 0) return -1;
}
if(h != 0) return -1;
int lb = 0, ub = 1000000;
while(lb < ub) {
int m = (lb + ub + 1) / 2;
vector <pii> v;
stack <int> H;
for(int i = 0; i < n; i++) {
if(s[i] == '!' && !v.empty()) {
v[v.size()-1].se++;
while(v[v.size()-1].se < m && i < n - 1 && s[i+1] == '!') {
i++, v[v.size()-1].se++;
}
if(v[v.size()-1].se == m) v.pop_back();
continue;
}
if(s[i] == 'C') {
bool flag = false;
while(!v.empty() && H.top() < v[v.size()-1].fi) {
if(v[v.size()-1].se < m) flag = true;
v.pop_back();
}
v.emplace_back(H.top(), 0);
if(flag) break;
H.pop();
}
if(s[i] == 'H') H.push(i);
while(!v.empty() && v[v.size()-1].se >= m) v.pop_back();
}
if(v.empty()) lb = m;
else ub = m-1;
}
return lb;
}
