#include<vector>
#include<algorithm>
#include "hiccup.h"
int HicCup(std::string S) {
int N = S.size();
int stack = 0;
int mark = 0;
std::vector<int> v;
for(auto i:S){
if(i == '!') mark++;
}
int left=0, right=mark, prev = 'H';
for(int i=0; i<N; i++){
if(S[i] == 'H') stack++;
if(S[i] == 'C'){
stack--;
if(stack < 0) return -1;
v.push_back(mark);
}
if(S[i] == '!') mark--;
if(S[i] == '!' && prev == 'H') return -1;
if(S[0]=='!') return -1;
prev = S[i];
}
while(left < right){
int mid = (left+right)/2;
int prev = v[0];
for(auto i:v){
prev = std::min(prev, i) - mid;
}
if(prev < 0) right = mid-1;
left = mid+1;
}
int ans = 0;
for(int mid=left-3; mid <= left+3; mid++){
int prev = v[0];
for(auto i:v){
prev = std::min(prev, i) - mid;
}
if(prev < 0) break;
ans = mid;
}
if(stack) return -1;
return ans;
}
