#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> static void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if(x < y) x = y; }

struct FenwickTree {
	typedef int T;
	vector<T> v;
	void init(int n) { v.assign(n, T()); }
	void add(int i, T x) {
		for(; i < (int)v.size(); i |= i + 1) v[i] += x;
	}
	T sum(int i) const {	//[0, i)
		T r = T();
		for(-- i; i >= 0; i = (i & (i + 1)) - 1) r += v[i];
		return r;
	}
	T sum(int left, int right) const {	//[left, right)
		return sum(right) - sum(left);
	}
};


int main() {
	string S;
	while(cin >> S) {
		int n = S.size();
		int cnt[26] = {};
		rep(i, n) ++ cnt[S[i] - 'a'];
		bool ok = true;
		rep(a, 26) ok &= cnt[a] % 2 == 0;
		if(!ok) {
			puts("-1");
			continue;
		}

		const int A = 26;
		vector<vi> indices(A);
		rep(i, n)
			indices[S[i] - 'a'].push_back(i);
		vector<pii> intervals(A);
		rep(a, A)
			intervals[a] = { 0, (int)indices[a].size() };
		ll ans = 0;
		FenwickTree ft;
		ft.init(n + 1);
		rep(k, n / 2) {
			int minCost = INF;
			int minA = -1, minL = -1, minR = -1;
			rep(a, A) {
				pii p = intervals[a];
				if(p.first == p.second) continue;
				int L = indices[a][p.first];
				int R = indices[a][p.second - 1];
				int l = L + ft.sum(L + 1);
				int r = R + ft.sum(R + 1);
				int cost = (l - k) + ((n - 1 - k) - r);
				if(minCost > cost) {
					minCost = cost;
					minA = a;
					minL = L;
					minR = R;
				}
			}
			ans += minCost;
			++ intervals[minA].first;
			-- intervals[minA].second;
			ft.add(0, +1);
			ft.add(minL, -1);
			ft.add(minR + 1, -1);
			ft.add(n, +1);
		}
		
		printf("%lld\n", ans);
	}
	return 0;
}
### Prompt

Please provide a cpp coded solution to the problem described below:

Problem

Given a string S of even length.
You can swap two adjacent characters in the string S as many times as you like.
How many operations do we need to do to make the string S a palindrome?
If it is not possible to make a palindrome, output -1.

Constraints

* 2 ≤ | S | ≤ 4 x 105
* All strings are composed of lowercase letters
* String length is even

Input

The input is given in the following format.


S


The string S is given on one line.

Output

Outputs the minimum number of operations to make the character string S a palindrome on one line. If it is not possible to make a palindrome, output -1 on one line instead.

Examples

Input

acca


Output

0


Input

acpcacpc


Output

3


Input

aizu


Output

-1

### Response

```cpp
#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> static void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if(x < y) x = y; }

struct FenwickTree {
	typedef int T;
	vector<T> v;
	void init(int n) { v.assign(n, T()); }
	void add(int i, T x) {
		for(; i < (int)v.size(); i |= i + 1) v[i] += x;
	}
	T sum(int i) const {	//[0, i)
		T r = T();
		for(-- i; i >= 0; i = (i & (i + 1)) - 1) r += v[i];
		return r;
	}
	T sum(int left, int right) const {	//[left, right)
		return sum(right) - sum(left);
	}
};


int main() {
	string S;
	while(cin >> S) {
		int n = S.size();
		int cnt[26] = {};
		rep(i, n) ++ cnt[S[i] - 'a'];
		bool ok = true;
		rep(a, 26) ok &= cnt[a] % 2 == 0;
		if(!ok) {
			puts("-1");
			continue;
		}

		const int A = 26;
		vector<vi> indices(A);
		rep(i, n)
			indices[S[i] - 'a'].push_back(i);
		vector<pii> intervals(A);
		rep(a, A)
			intervals[a] = { 0, (int)indices[a].size() };
		ll ans = 0;
		FenwickTree ft;
		ft.init(n + 1);
		rep(k, n / 2) {
			int minCost = INF;
			int minA = -1, minL = -1, minR = -1;
			rep(a, A) {
				pii p = intervals[a];
				if(p.first == p.second) continue;
				int L = indices[a][p.first];
				int R = indices[a][p.second - 1];
				int l = L + ft.sum(L + 1);
				int r = R + ft.sum(R + 1);
				int cost = (l - k) + ((n - 1 - k) - r);
				if(minCost > cost) {
					minCost = cost;
					minA = a;
					minL = L;
					minR = R;
				}
			}
			ans += minCost;
			++ intervals[minA].first;
			-- intervals[minA].second;
			ft.add(0, +1);
			ft.add(minL, -1);
			ft.add(minR + 1, -1);
			ft.add(n, +1);
		}
		
		printf("%lld\n", ans);
	}
	return 0;
}
```