#include "hiccup.h"
#include <bits/stdc++.h>
using namespace std;
int N;
std::string S;
int myS[1000010];
int top;
int state[1000010];
bool able(int v)
{
top = 0;
for (int i = 0; i < N; i++)
{
top++;
if (S[i] == 'H')
state[top] = 1;
if (S[i] == 'C')
{
if (state[top - 1] == 1)
state[top] = 2;
else return false;
}
if (S[i] == '!')
{
if (state[top - 1] <= 1) top--;
else state[top] = state[top - 1] + 1;
}
if (state[top] == v + 2)
top -= v + 2;
}
return state[top] == 0;
}
int HicCup(std::string S_) {
S = S_;
N = S.size();
stack <int> ST;
for (int i = 0; i < N; i++)
{
if (S[i] == 'H') ST.push(i);
if (S[i] == 'C')
{
if (ST.empty()) return -1;
myS[ST.top()] = i;
ST.pop();
}
}
if (!ST.empty()) return -1;
for (int i = 0; i < N; i++)
if (S[i] == '!')
{
if (i == 0) return -1;
if (S[i - 1] == 'H') return -1;
}
int s, e, v;
s = 0; e = (1 << 20) - 1;
while (s < e)
{
v = (s + e) / 2;
if (able(v + 1)) s = v + 1;
else e = v;
}
return s;
}
