#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;
vector<long long> quu;
while (stk.top() != -1)
quu.push_back(stk.top()), ttl += stk.top(), cnt++, stk.pop();
stk.pop();
if (cnt)
{
long long avg = ttl / cnt;
for (int i = 0; i < cnt - 1; i++)
if (quu[i] < avg)
ans = min(ans, quu[i]);
else
quu[i + 1] += quu[i] - avg, quu[i] = avg;
ans = min(ans, min(quu[cnt - 1], avg));
}
i++;
cnt = 0;
while (s[i] == '!' && i < (int)s.size())
cnt++, i++;
i--;
stk.push(cnt);
}
}
long long ttl = 0, cnt = 0;
vector<long long> quu;
while (!stk.empty())
quu.push_back(stk.top()), ttl += stk.top(), cnt++, stk.pop();
if (cnt)
{
long long avg = ttl / cnt;
for (int i = 0; i < cnt - 1; i++)
if (quu[i] < avg)
ans = min(ans, quu[i]);
else
quu[i + 1] += quu[i] - avg, quu[i] = avg;
ans = min(ans, min(quu[cnt - 1], avg));
}
return (int)ans;
}
