#include "hiccup.h"
using namespace std;
char ch[1010101];
int am[1010101], scn;
bool isok(int N, string &S, int K){
scn=0;
for(int i=0; i<N; i++){
if(S[i]=='H') ch[scn]='H', am[scn++]=0;
if(S[i]=='C'){
while(1){
if(!scn || ch[scn-1]=='C') return 0;
scn--;
if(ch[scn]=='H') break;
if(ch[scn]=='X' && am[scn]) return 0;
}
if(scn && ch[scn-1]=='X') am[scn-1]+=K;
else ch[scn]='X', am[scn++]=K;
}
if(S[i]=='!'){
if(!scn || ch[scn-1]!='X') return 0;
am[scn-1]--;
if(am[scn-1]<0) am[scn-1]=0;
}
}
while(scn){
scn--;
if(ch[scn]=='H' || ch[scn]=='C') return 0;
if(ch[scn]=='X' && am[scn]) return 0;
}
return 1;
}
int HicCup(int N, string S) {
int mi=0, mx=N, md, dap=-1;
while(mi<=mx){
md=(mi+mx)/2;
if(isok(N, S, md)) dap=md, mi=md+1;
else mx=md-1;
}
return dap;
}
