#include "hiccup.h"
#include <algorithm>
#include <string>
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;
}
int l=1, r=N, res=0;
while(l<=r){
int m = (l+r)/2;
int cur = 0;
int curcur = 0;
for(int i=0; i<N; i++){
if(S[i] == 'C') cur++;
else if(S[i] == '!'){
if(cur){
curcur++;
if(curcur == m){
curcur = 0;
cur--;
}
}
}
}
if(cur) r = m-1;
else l = m+1, res = m;
}
return res;
}
