#include "hiccup.h"
#include <vector>
using namespace std;
int HicCup(std::string S) {
int N = S.size();
int l = -1, r = N;
while (l + 1 < r){
int m = (l + r) / 2;
vector<pair<char, int> > u;
bool good = true;
for (int i = 0; i < N; i++){
if (S[i] == 'H'){
u.push_back({ S[i],1 });
}
else if (S[i] == 'C'){
if (!u.empty() && u.back().first == 0) u.pop_back();
u.push_back({ S[i],1 });
}
else{
if (!u.empty() && u.back().first == '!'){
u.back().second++;
}
else if (!u.empty() && u.back().first == 0){
u.back().second++;
}
else{
u.push_back({ '!',1 });
}
}
while (1){
int z = u.size();
if (m == 0){
if (z >= 2 && u[z - 2].first == 'H' && u[z - 1].first == 'C'){
u.pop_back();
u.pop_back();
if (!u.empty() && u.back().first == 0);
else u.push_back({ 0,0 });
}
else break;
}
else{
if (z >= 3 && u[z - 3].first == 'H' && u[z - 2].first == 'C' && u[z - 1].first == '!' && u[z - 1].second >= m){
u.pop_back();
u.pop_back();
u.pop_back();
if (!u.empty() && u.back().first == 0);
else u.push_back({ 0,0 });
}
else if (z >= 3 && u[z - 3].first == 'H' && u[z - 2].first == 'C' && u[z - 1].first == 0 && u[z - 1].second >= m){
u.pop_back();
u.pop_back();
u.pop_back();
if (!u.empty() && u.back().first == 0);
else u.push_back({ 0,0 });
}
else if (z >= 4 && u[z - 4].first == 'H' && u[z - 3].first == 'C' && u[z - 2].first == 0 && u[z - 1].first == '!' && u[z - 2].second + u[z - 1].second >= m){
int r = u[z - 2].second + u[z - 1].second - m;
u.pop_back();
u.pop_back();
u.pop_back();
u.pop_back();
if (!u.empty() && u.back().second == 0) u.back().second += r;
else u.push_back({ 0,r });
}
else if (z >= 4 && u[z - 4].first == 'H' && u[z - 3].first == 'C' && u[z - 2].first == '!' && u[z - 1].first == 0 && u[z - 2].second + u[z - 1].second >= m){
int r = u[z - 2].second + u[z - 1].second - m;
u.pop_back();
u.pop_back();
u.pop_back();
u.pop_back();
if (!u.empty() && u.back().second == 0) u.back().second += r;
else u.push_back({ 0,r });
}
else break;
}
while (u.size() >= 2){
z = u.size();
if (u[z - 2].first == 0 && (u[z - 1].first == '!' || u[z - 1].first == 0)){
u[z - 2].second += u[z - 1].second;
u.pop_back();
}
else break;
}
}
}
while (!u.empty() && u.back().first == 0) u.pop_back();
if (!u.empty()) good = false;
if (good) l = m;
else r = m;
}
return l;
}
