#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
using namespace std;
typedef long long ll;
#include "hiccup.h"
vector<int> nums[1000006];
vector<int> v;
bool ok(int x, int id){
v = nums[id];
int N = v.size();
int r = N - 1;
fr(i, 0, N){
if(v[i] < x){
for(int j = r; j > i; j --){
if(v[j] - x >= x - v[i]){
v[i] = x;
v[j] -= (x - v[i]);
r = j;
break;
}
}
if(v[i] < x) return false;
}
}
return true;
}
int HicCup(std::string s) {
int n = s.size();
int cnt[n];
int c = 0;
for(int i = n - 1; i >= 0; i --){
if(s[i] == '!') c ++;
cnt[i] = c;
if(s[i] == 'C') c = 0;
else if(s[i] == 'H' && c > 0) return -1;
}
if(c > 0) return -1;
stack <int> S;
S.push(0);
int ANS = n;
fr(i, 0, n){
if(s[i] == 'H') S.push(i + 1);
else if(s[i] == 'C'){
if((int)(S.size()) == 1) return -1;
int id = S.top();
S.pop();
nums[(int)S.top()].pb(cnt[i]);
if(nums[id].empty()) continue;
int k = 0;
for(int b = ANS / 2; b >= 1; b /= 2){
while(k + b <= ANS && ok(k + b, id)) k += b;
}
ANS = min(ANS, k);
}
}
if((int)S.size() > 1)return -1;
if(!nums[0].empty()){
int k = 0;
for(int b = (ANS+1) / 2; b >= 1; b /= 2){
while(k + b <= ANS && ok(k + b, 0)) k += b;
}
ANS = min(ANS, k);
}
return ANS;
}/*
int main(){
<< HicCup("HC!!HHC!HC!!!C!!!");
}
*/
