#include <bits/stdc++.h>
#include "hiccup.h"
using namespace std;
const int INF = (int)1e9 + 5;
int Solve(int left, int right, const string &s, const vector<int> &lft) {
if (left > right) {
return INF;
}
if (s[left] == '!') {
return -1;
}
int cnt_excl = 0, cnt_intervals = 0, ans = INF;
for (int i = right; i >= left; --i) {
if (s[i] == '!') {
++cnt_excl;
} else {
assert(s[i] == 'C');
++cnt_intervals;
ans = min({ans, Solve(lft[i] + 1, i - 1, s, lft), cnt_excl / cnt_intervals});
i = lft[i];
}
}
return ans;
}
int HicCup(string s) {
int n = s.length();
vector<int> h_pos, lft(n);
for (int i = 0; i < n; ++i) {
if (s[i] == 'H') {
h_pos.emplace_back(i);
} else if (s[i] == 'C') {
if (h_pos.empty()) return -1;
lft[i] = h_pos.back();
h_pos.pop_back();
}
}
if (!h_pos.empty()) return -1;
return Solve(0, n - 1, s, lft);
}
