#include "hiccup.h"
#include <stack>
#include <vector>
#include <iostream>
using namespace std;
bool try_to_pop(stack<pair<int,int>> &st, int X){
// we want H_a C_b where a<=0 and b>=X
if(st.size() < 2) return false;
auto [b1, b2] = st.top(); st.pop();
auto [a1, a2] = st.top(); st.pop();
if(a1 != 1 || b1 != 2 || a2 > 0 || abs(b2) < X){
st.push({a1,a2}); st.push({b1,b2});
return false;
}
// combine ??(-a2) with !!(b2-X)
int newex = -a2 + abs(b2)-X;
if(st.empty()) st.push({0, -newex});
else if(st.top().second > 0) st.top().second+= newex;
else st.top().second-= newex;
return true;
}
bool possible(vector<pair<int,int>> &V, int X){
stack<pair<int,int>> st;
for(auto [ct, ex]: V){
st.push({ct,ex});
while(try_to_pop(st, X));
}
if(st.empty()) return true;
if(st.size() > 1) return false;
return st.top().first == 0 && st.top().second <= 0;
}
int HicCup(std::string S) {
int N = S.size();
vector<pair<int,int>> V;
// first: type. blank 0, H 1, C 2
// second: !
for(char c: S){
if(c == '!'){
if(V.empty()) V.push_back({0, 1});
else V.back().second++;
}
else if(c == 'H') V.push_back({1, 0});
else V.push_back({2, 0});
}
//for(auto [a,b]: V) cout<<a<<' '<<b<<endl;
int lo = 0, hi = 1000000, ans = -1;
while(lo <= hi){
int mid = (lo+hi)/2;
//cout<<"TRYING "<<mid<<endl;
if(possible(V, mid)) ans = mid, lo = mid+1;
else hi = mid-1;
}
if(ans > -1) return ans;
return -1;
}
