#include "hiccup.h"
#include <bits/stdc++.h>
using namespace std;
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 <int> v;
for(int i = 0; i < n; i++) {
if(s[i] == '!' && !v.empty()) {
v[v.size()-1]++;
while(v[v.size()-1] < m && i < n - 1 && s[i+1] == '!') {
i++, v[v.size()-1]++;
}
if(v[v.size()-1] == m) v.pop_back();
continue;
}
else if(!v.empty()) {
if(v[v.size()-1] < m) break;
v.pop_back();
}
if(s[i] == 'C') v.push_back(0);
}
if(v.empty()) lb = m;
else ub = m-1;
}
return lb;
}
