#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 p2 = v.size() - 1;
int p1 = 0;
int N = v.size();
while(p1 <= p2){
while(p1 < N && v[p1] >= x) p1 ++;
while(p2 >= 0 && v[p2] == x) p2 --;
if(p1 > p2) break;
if(p1 == p2) return false;
if(v[p2] - x >= x - v[p1]){
v[p2] -= (x - v[p1]);
v[p1] = x;
}
else{
p2 --;
}
}
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 / 2; b >= 1; b /= 2){
while(k + b <= ANS && ok(k + b, 0)) k += b;
}
ANS = min(ANS, k);
}
return ANS;
}/*
int main(){
cout << HicCup("HC!!HHC!HC!!!C!!!");
}
*/
