#include "hiccup.h"
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
using namespace std;
int HicCup(std::string S) {
int N = S.size();
int mask = 0;
int bal = 0;
for(int i=0; i<N; i++){
if(S[i] == '!' && mask != 3) return -1;
if(S[i] == 'H') bal++, mask |= 1;
if(S[i] == 'C') bal--, mask |= 2;
if(bal < 0) return -1;
}
if(bal > 0) return -1;
int cur[N], curcur[N], maskk[N];
int l=1, r=N, res=0;
while(l<=r){
int mid=(l+r)/2;
int ok = 1;
int level = 0;
cur[level] = 0;
curcur[level] = 0;
maskk[level] = 0;
for(int i=0; i<N; i++){
if(S[i] == 'H'){
maskk[level] |= 1;
level++;
cur[level] = 0;
curcur[level] = 0;
maskk[level] = 0;
} else if(S[i] == 'C'){
if(cur[level] != 0){
ok = 0;
break;
}
level--;
cur[level]++;
maskk[level] |= 2;
} else{
if(level == -1) return -1;
if(maskk[level] != 3) return -1;
if(cur[level]){
curcur[level]++;
if(curcur[level] == mid){
cur[level]--;
curcur[level] = 0;
}
}
}
}
if(cur[0] == 0 && ok) res = mid, l = mid+1;
else r = mid-1;
}
return res;
}
