#include "hiccup.h"
#include <algorithm>
#include <vector>
#include <tuple>
using namespace std;
typedef pair<int, int> pii;
int n;
char S[1000001];
int nxt[1000002];
int prv[1000002];
vector<pii> P;
bool check(int x) {
for (int i = 1; i <= n; ++i) {
nxt[i] = i + 1;
prv[i] = i - 1;
}
for (pii _i : P) {
int a, b;
tie(a, b) = _i;
int cnt = 0, i;
for (i = nxt[b]; cnt < x && i <= n && S[i] == '!'; i = nxt[i], ++cnt);
if (cnt < x) return 0;
if (nxt[a] == b) {
nxt[prv[a]] = i;
prv[i] = prv[a];
}
else {
nxt[prv[a]] = nxt[a];
prv[nxt[a]] = prv[a];
nxt[prv[b]] = i;
prv[i] = prv[b];
}
}
return 1;
}
int HicCup(string _S) {
n = _S.length();
vector<int> st;
S[0] = 'H';
for (int i = 0; i < n; ++i) {
S[i + 1] = _S[i];
if (S[i + 1] == 'H') st.push_back(i + 1);
else if (S[i + 1] == 'C') {
if (st.empty()) return -1;
P.emplace_back(st.back(), i + 1);
st.pop_back();
}
if (S[i] == 'H' && S[i + 1] == '!') return -1;
}
if (!st.empty()) return -1;
if (P.empty()) return -1;
int s = 0, e = n;
sort(P.begin(), P.end(), [&](pii a, pii b) {
return a.first > b.first;
});
while (s < e) {
int m = (s + e + 1) / 2;
if (check(m)) s = m;
else e = m - 1;
}
return s;
}
