#include "hiccup.h"
#include <bits/stdc++.h>
using namespace std;
int a[1000000];
bool chk(string &s, int l, int r, int x, int b=0) {
if(l>r)
return 1;
while(s[r]=='!') {
--r;
++b;
}
b-=x;
if(b<0)
return 0;
return chk(s, a[r]+1, r-1, x)&&chk(s, l, a[r]-1, x, b);
}
int HicCup(string s) {
int n=s.size();
//check correctness
if(s[0]=='!')
return -1;
for(int i=0; i+1<n; ++i)
if(s[i]=='H'&&s[i+1]=='!')
return -1;
//bracket matching
vector<int> t;
for(int i=0; i<n; ++i) {
if(s[i]=='H')
t.push_back(i);
else if(s[i]=='C') {
if(t.empty())
return -1;
a[i]=t.back();
t.pop_back();
}
}
if(t.size())
return -1;
int lb=0, rb=n;
while(lb<rb) {
int mb=(lb+rb+1)/2;
if(chk(s, 0, n-1, mb))
lb=mb;
else
rb=mb-1;
}
return lb;
}
