#include "hiccup.h"
#include <bits/stdc++.h>
using namespace std;
int r[1000005], l[1000005];
string s;
bool solve(int st, int dr, int mij){
int nr = 0;
for(int i = dr; i >= st ; --i){
if(s[i] == 'C'){
bool ok = solve(l[i] + 1, i - 1, mij);
if(!ok) return 0;
i = l[i];
nr -= mij;
if(nr < 0) return 0;
}
else if(s[i] == '!') ++nr;
}
return 1;
}
int HicCup(std::string S) {
s = S;
int N = S.size();
int nrH = 0, nrC = 0;
for(auto i : S){
if(i == '!' && (nrH == 0 || nrC == 0)) return -1;
else if(i == 'H') ++nrH;
else if(i == 'C'){
++nrC;
if(nrC > nrH) return -1;
}
}
for(int i = 0; i < N - 1 ; ++i)
if(S[i] == 'H' && S[i + 1] == '!') return -1;
if(nrH != nrC) return -1;
for(int i = 0; i < N ; ++i){
int nr = 0;
while(i < N && S[i] == 'H') ++nr, ++i;
if(nr < 2) continue ;
nr = 0;
while(i < N && S[i] == 'C') ++nr, ++i;
if(nr >= 2) return 0;
}
stack <int> sto;
for(int i = 0; i < N ; ++i){
if(S[i] == 'H') sto.push(i);
else if(S[i] == 'C'){
r[sto.top()] = i;
l[i] = sto.top();
sto.pop();
}
}
int st = 0, dr = N;
while(st <= dr){
int mij = (st + dr) / 2;
bool ok = solve(0, N - 1, mij);
if(ok) st = mij + 1;
else dr = mij - 1;
}
return dr;
}
