#include "hiccup.h"
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
using namespace std;
int HicCup(std::string S) {
int N = S.size();
stack<int> st[N+2];
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 l=1, r=N, res=0;
while(l<=r){
int mid=(l+r)/2;
int ok = 1;
int level = 0;
while(!st[0].empty()) st[0].pop();
for(int i=0; i<N; i++){
if(S[i] == 'H'){
level++;
while(!st[level].empty()) st[level].pop();
} else if(S[i] == 'C'){
if(st[level].size()){
ok = 0;
break;
}
level--;
st[level].push(0);
} else{
if(level == -1) return -1;
if(st[level].size()){
int x = st[level].top();
x++;
st[level].pop();
if(x != mid){
st[level].push(x);
}
}
}
}
if(st[0].empty() && ok) res = mid, l = mid+1;
else r = mid-1;
}
return res;
}
