1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include<bits/stdc++.h>
using namespace std;
using LL=long long;
#define FOR(i,l,r) for(int i=(l);i<=(r);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ssize(x) int(x.size())
template<class A,class B>auto&operator<<(ostream&o,pair<A,B>p){return o<<'('<<p.first<<", "<<p.second<<')';}
template<class T>auto operator<<(ostream&o,T x)->decltype(x.end(),o){o<<'{';int i=0;for(auto e:x)o<<(", ")+2*!i++<<e;return o<<'}';}
#ifdef DEBUG
#define debug(x...) cerr<<"["#x"]: ",[](auto...$){((cerr<<$<<"; "),...);}(x),cerr<<'\n'
#else
#define debug(...) {}
#endif

struct Fenwick {
	vector<LL> s;
	Fenwick(int n) : s(n) {}
	void update(int pos, LL val) {
		for(; pos < ssize(s); pos |= pos + 1)
			s[pos] += val;
	}
	LL query(int pos) {
		LL ret = 0;
		for(pos++; pos > 0; pos &= pos - 1)
			ret += s[pos - 1];
		return ret;
	}
	LL query(int l, int r) {
		return query(r) - query(l - 1);
	}
};

struct RangeAdd {
	Fenwick f;
	RangeAdd(int n) : f(n) {}
	void update(int l, int r, LL val) {
		f.update(l, val);
		f.update(r + 1, -val);
	}
	LL query(int pos) {
		return f.query(pos);
	}
};

int main() {
	cin.tie(0)->sync_with_stdio(0);

	string s;
	cin >> s;
	vector<int> v(s.begin(), s.end());
	for (auto& e : v)
		e -= 'a';
	const int n = ssize(v);
	debug(n, v);

	const int cnt1 = accumulate(v.begin(), v.end(), 0);
	const int cnt0 = n - cnt1;
	if (cnt0 % 2 and cnt1 % 2) {
		cout << -1 << '\n';
		return 0;
	}
	if (cnt0 == 0 or cnt1 == 0) {
		cout << 0 << '\n';
		return 0;
	}

	LL ans = 0;
	int left = 0, right = n - 1;
	vector<int> tree_left = {0, 0};
	vector<int> tree_right = {cnt0 - 1, cnt1 - 1};
	vector<RangeAdd> tree = {RangeAdd(cnt0), RangeAdd(cnt1)};
	{
		vector<int> cnt = {0, 0};
		REP(i, n) {
			const int pos = cnt[v[i]];
			tree[v[i]].update(pos, pos, i);
			++cnt[v[i]];
		}
	}
	while (left < right) {
		debug(ans, left, right);
		debug(tree_left, tree_right);

		const int type = tree[0].query(tree_left[0]) != left;

		if (tree_left[type] == tree_right[type]) {
			ans += (left + right) / 2 - tree[type].query(tree_left[type]);
			break;
		}

		const int pos_right = int(tree[type].query(tree_right[type]));
		ans += right - pos_right;
		
		const int update_right = tree_right[type ^ 1];
		int update_left = update_right + 1;

		int bb = tree_left[type ^ 1], ee = tree_right[type ^ 1];
		while (bb <= ee) {
			const int ss = (bb + ee) / 2;
			if (tree[type ^ 1].query(ss) > pos_right) {
				update_left = ss;
				ee = ss - 1;
			}
			else {
				bb = ss + 1;
			}
		}

		if (update_left <= update_right) {
			tree[type ^ 1].update(update_left, update_right, -1);
		}

		++tree_left[type];
		--tree_right[type];
		if (tree_left[type] > tree_right[type])
			break;

		++left;
		--right;
	}

	cout << ans << '\n';
}