#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 l=1, r=N, res=0;
while(l<=r){
int mid=(l+r)/2;
stack<int> st;
for(int i=0; i<N; i++){
if(S[i] == 'C'){
st.push(0);
} else if(S[i] == '!'){
if(st.size()){
int x = st.top();
st.pop();
x++;
if(x < mid){
st.push(x);
}
}
}
}
if(st.empty()) res = mid, l = mid+1;
else r = mid-1;
}
return res;
}
