#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}

struct BIT{
	int N;
	vector<int> bit;
	void init(int n){
		N=n;
		bit.resize(n+1);
	}
	int sum(int i){		//i?????????a[0]+..a[i-1]
		int s=0;
		while(i>0){
			s+=bit[i];
			i-=(i&-i);
		}
		return s;
	}
	void add(int i,int x){	//a[i]+=x (0-indexed)
		i++;
		while(i<=N){
			bit[i]+=x;
			i+=(i&-i);
		}
	}
}bit;

int cnt[26],cnthalf[26];
int N;
typedef long long ll;
vector<int> c2p[26];
bool moved[400000];
ll getinversion(vector<int> a){
	int N=a.size();
	vector<int> p(N);
	rep(i,N) p[a[i]]=i;
	ll ret=0;
	bit.init(N);
	rep(i,N) bit.add(i,1);
	rep(i,N){
		ret+=bit.sum(p[i]);
		bit.add(p[i],-1);
	}
	return ret;
}
ll calc(string a,string b){
	assert(a.size()==b.size());
	int N=a.size();
	vector<int> A(N),B(N),iB(N);
	int I=0;
	rep(c,26){
		int J=I;
		rep(i,N){
			if(a[i]=='a'+c) A[i]=I++;
			if(b[i]=='a'+c) B[i]=J++;
		}
	}
	rep(i,N) iB[B[i]]=i;
	rep(i,N) B[iB[A[i]]]=i;
	return getinversion(B);
}
ll solve(){
	string s;
	cin>>s;
	N=s.size();
	rep(i,N){
		if(i==N/2){
			rep(j,26) cnthalf[j]=cnt[j];
		}
		cnt[s[i]-'a']++;
		c2p[s[i]-'a'].pb(i);
	}
	rep(i,26) if(cnt[i]%2) return -1;
	vector<int> le,ri;
	rep(i,26){
		if(cnthalf[i]<cnt[i]/2){	//ri to le
			for(int j=cnthalf[i];j<cnt[i]/2;j++) ri.pb(c2p[i][j]);
		}else{
			for(int j=cnt[i]/2;j<cnthalf[i];j++) le.pb(c2p[i][j]);
		}
	}
	sort(all(ri));
	sort(all(le));
	assert(le.size()==ri.size());
	int K=le.size();
	ll ans=(ll)K*K;
	rep(i,K) ans+=N/2-1-le[K-1-i]-i;
	rep(i,K) ans+=ri[i]-N/2-i;
	rep(i,K) moved[le[i]]=moved[ri[i]]=1;
	string a,b;
	rep(i,N/2) if(!moved[i]) a+=s[i];
	rep(i,K) a+=s[ri[i]];
	rep(i,K) b+=s[le[i]];
	rep(i,N/2) if(!moved[i+N/2]) b+=s[i+N/2];
	reverse(all(b));
	ans+=calc(a,b);
	return ans;
}
int main(){
	cout<<solve()<<endl;
}
### Prompt

Your task is to create a Cpp solution to the following problem:

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 rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}

struct BIT{
	int N;
	vector<int> bit;
	void init(int n){
		N=n;
		bit.resize(n+1);
	}
	int sum(int i){		//i?????????a[0]+..a[i-1]
		int s=0;
		while(i>0){
			s+=bit[i];
			i-=(i&-i);
		}
		return s;
	}
	void add(int i,int x){	//a[i]+=x (0-indexed)
		i++;
		while(i<=N){
			bit[i]+=x;
			i+=(i&-i);
		}
	}
}bit;

int cnt[26],cnthalf[26];
int N;
typedef long long ll;
vector<int> c2p[26];
bool moved[400000];
ll getinversion(vector<int> a){
	int N=a.size();
	vector<int> p(N);
	rep(i,N) p[a[i]]=i;
	ll ret=0;
	bit.init(N);
	rep(i,N) bit.add(i,1);
	rep(i,N){
		ret+=bit.sum(p[i]);
		bit.add(p[i],-1);
	}
	return ret;
}
ll calc(string a,string b){
	assert(a.size()==b.size());
	int N=a.size();
	vector<int> A(N),B(N),iB(N);
	int I=0;
	rep(c,26){
		int J=I;
		rep(i,N){
			if(a[i]=='a'+c) A[i]=I++;
			if(b[i]=='a'+c) B[i]=J++;
		}
	}
	rep(i,N) iB[B[i]]=i;
	rep(i,N) B[iB[A[i]]]=i;
	return getinversion(B);
}
ll solve(){
	string s;
	cin>>s;
	N=s.size();
	rep(i,N){
		if(i==N/2){
			rep(j,26) cnthalf[j]=cnt[j];
		}
		cnt[s[i]-'a']++;
		c2p[s[i]-'a'].pb(i);
	}
	rep(i,26) if(cnt[i]%2) return -1;
	vector<int> le,ri;
	rep(i,26){
		if(cnthalf[i]<cnt[i]/2){	//ri to le
			for(int j=cnthalf[i];j<cnt[i]/2;j++) ri.pb(c2p[i][j]);
		}else{
			for(int j=cnt[i]/2;j<cnthalf[i];j++) le.pb(c2p[i][j]);
		}
	}
	sort(all(ri));
	sort(all(le));
	assert(le.size()==ri.size());
	int K=le.size();
	ll ans=(ll)K*K;
	rep(i,K) ans+=N/2-1-le[K-1-i]-i;
	rep(i,K) ans+=ri[i]-N/2-i;
	rep(i,K) moved[le[i]]=moved[ri[i]]=1;
	string a,b;
	rep(i,N/2) if(!moved[i]) a+=s[i];
	rep(i,K) a+=s[ri[i]];
	rep(i,K) b+=s[le[i]];
	rep(i,N/2) if(!moved[i+N/2]) b+=s[i+N/2];
	reverse(all(b));
	ans+=calc(a,b);
	return ans;
}
int main(){
	cout<<solve()<<endl;
}
```