#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,b) FOR(i,0,b)
#define PB push_back
#define ALL(c) c.begin(),c.end()
#define cat// cout << __LINE__ << endl;
using namespace std;
typedef long long LL;
typedef int ut;
typedef pair<ut,ut> pr;
typedef vector<ut> VI;
typedef vector<pr> Vpr;
typedef priority_queue<pr,Vpr,greater<pr> > PQ;
const int SIZE=1e6;
//const ut INF=1LL<<60;
int BIT[SIZE];
int pairs[SIZE];
int times[SIZE];
LL ans=0;
int sum(int x){
	int ans=0;
	while(x>0){
		ans+=BIT[x];
		x-=x&-x;
	}
	return ans;
}
void add(int x,int p){
	while(x<=SIZE){
		BIT[x]+=p;
		x+=x&-x;
	}
}
int sum(int a,int b){
	if(a<=b) return sum(b)-sum(a-1);
	return 0;
}
void pairing(string s){
	FOR(i,'a','z'+1){
		vector<int> v;
		REP(j,s.size()){
			if(s[j]==i){
				v.PB(j);
			}			
		}
		REP(i,v.size()/2){
			int rev=v.size()-i-1;
			pairs[v[i]+1]=v[rev]+1;
			pairs[v[rev]+1]=v[i]+1;
			ans-=abs(v[i]-v[v.size()-i-1])-1;
		}
	}
}
int main(){
	string s;
	cin >> s;
	REP(i,s.size()){
		times[s[i]-'a']++;
	}
	int odds=0;
	REP(i,'z'-'a'+1){
		odds+=times[i]&1;
	}
	if(odds>=1){
		cout << -1 << endl;
		return 0;
	}
	LL pnum=s.size()/2;
	ans+=pnum*(pnum-1);
	//cout << ans << endl;
	pairing(s);
	FOR(i,1,s.size()+1){
		if(pairs[i]<i) {
			add(pairs[i],-1);
			ans+=sum(pairs[i]+1,i-1);
		}
		else{
			add(i,1);
		}

	}
	cout << ans << endl;
	return 0;

}
### Prompt

Develop a solution in cpp 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>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,b) FOR(i,0,b)
#define PB push_back
#define ALL(c) c.begin(),c.end()
#define cat// cout << __LINE__ << endl;
using namespace std;
typedef long long LL;
typedef int ut;
typedef pair<ut,ut> pr;
typedef vector<ut> VI;
typedef vector<pr> Vpr;
typedef priority_queue<pr,Vpr,greater<pr> > PQ;
const int SIZE=1e6;
//const ut INF=1LL<<60;
int BIT[SIZE];
int pairs[SIZE];
int times[SIZE];
LL ans=0;
int sum(int x){
	int ans=0;
	while(x>0){
		ans+=BIT[x];
		x-=x&-x;
	}
	return ans;
}
void add(int x,int p){
	while(x<=SIZE){
		BIT[x]+=p;
		x+=x&-x;
	}
}
int sum(int a,int b){
	if(a<=b) return sum(b)-sum(a-1);
	return 0;
}
void pairing(string s){
	FOR(i,'a','z'+1){
		vector<int> v;
		REP(j,s.size()){
			if(s[j]==i){
				v.PB(j);
			}			
		}
		REP(i,v.size()/2){
			int rev=v.size()-i-1;
			pairs[v[i]+1]=v[rev]+1;
			pairs[v[rev]+1]=v[i]+1;
			ans-=abs(v[i]-v[v.size()-i-1])-1;
		}
	}
}
int main(){
	string s;
	cin >> s;
	REP(i,s.size()){
		times[s[i]-'a']++;
	}
	int odds=0;
	REP(i,'z'-'a'+1){
		odds+=times[i]&1;
	}
	if(odds>=1){
		cout << -1 << endl;
		return 0;
	}
	LL pnum=s.size()/2;
	ans+=pnum*(pnum-1);
	//cout << ans << endl;
	pairing(s);
	FOR(i,1,s.size()+1){
		if(pairs[i]<i) {
			add(pairs[i],-1);
			ans+=sum(pairs[i]+1,i-1);
		}
		else{
			add(i,1);
		}

	}
	cout << ans << endl;
	return 0;

}
```