#include<bits/stdc++.h>
#include "hiccup.h"
using namespace std;
bool chk(string s)
{
if (s[0] == '!')
return false;
for (int i = 1; i < (int)s.size(); i++)
if (s[i] == '!' && s[i - 1] == 'H')
return false;
stack<char> stk;
for (int i = 0; i < (int)s.size(); i++)
if (s[i] == '!')
continue;
else if (stk.empty())
stk.push(s[i]);
else if (stk.top() == 'H' && s[i] == 'C')
stk.pop();
else
stk.push(s[i]);
return stk.empty();
}
int HicCup(string s)
{
long long N = s.size();
if (!chk(s))
return -1;
long long ans = N;
stack<long long> stk;
for (int i = 0; i < (int)s.size(); i++)
{
if (s[i] == 'H')
stk.push(-1);
else
{
long long ttl = 0, cnt = 0;
while (stk.top() != -1)
ttl += stk.top(), cnt++, stk.pop();
stk.pop();
if (cnt)
ans = min(ans, ttl / cnt);
i++;
cnt = 0;
while (s[i] == '!' && i < (int)s.size())
cnt++, i++;
i--;
stk.push(cnt);
}
}
long long ttl = 0, cnt = 0;
while (!stk.empty())
ttl += stk.top(), cnt++, stk.pop();
ans = min(ans, ttl / cnt);
return (int)ans;
}
