#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define REP(i,b) FOR(i,0,b)
#define PB push_back

using ll=long long;
using pii=pair<int,int>;
using vi=vector<int>;

int read(){
	int i;
	scanf("%d",&i);
	return i;
}

const int Nmax=514893;
struct Bit{
	int data[Nmax],s;
	void Init(int n){
		s=n;
		fill(data,data+s,0);
	}
	void Add(int i,int v){
		while(i<s){
			data[i]+=v;
			i+=(i+1)&(-i-1);
		}
	}
	int Get(int i){
		int ret=0;
		while(i>=0){
			ret+=data[i];
			i-=(i+1)&(-i-1);
		}
		return ret;
	}
} bit;

char tmp[Nmax];
int str[Nmax],src[Nmax],dst[Nmax];
int c1[26],c2[26];
queue<int> g[26];

int main(){
	scanf("%s",tmp);
	int n=strlen(tmp);
	REP(i,n){
		str[i]=tmp[i]-'a';
		c1[str[i]]++;
	}
	REP(i,26)
		if(c1[i]&1){
			cout<<-1<<endl;
			return 0;
		}
	ll ans=0;
	int ss=0,ds=0;
	REP(i,n){
		if((++c2[str[i]])*2<=c1[str[i]]){
			src[ss++]=str[i];
			ans+=ds;
		}else{
			dst[ds++]=str[i];
		}
	}
	reverse(dst,dst+n/2);
	REP(i,n/2)
		g[src[i]].push(i);
	bit.Init(n/2);
	REP(i,n/2){
		int x=g[dst[i]].front();g[dst[i]].pop();
		ans+=x-i+bit.Get(x);
		bit.Add(0,1);
		bit.Add(x,-1);
	}
	cout<<ans<<endl;
}
### 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>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define REP(i,b) FOR(i,0,b)
#define PB push_back

using ll=long long;
using pii=pair<int,int>;
using vi=vector<int>;

int read(){
	int i;
	scanf("%d",&i);
	return i;
}

const int Nmax=514893;
struct Bit{
	int data[Nmax],s;
	void Init(int n){
		s=n;
		fill(data,data+s,0);
	}
	void Add(int i,int v){
		while(i<s){
			data[i]+=v;
			i+=(i+1)&(-i-1);
		}
	}
	int Get(int i){
		int ret=0;
		while(i>=0){
			ret+=data[i];
			i-=(i+1)&(-i-1);
		}
		return ret;
	}
} bit;

char tmp[Nmax];
int str[Nmax],src[Nmax],dst[Nmax];
int c1[26],c2[26];
queue<int> g[26];

int main(){
	scanf("%s",tmp);
	int n=strlen(tmp);
	REP(i,n){
		str[i]=tmp[i]-'a';
		c1[str[i]]++;
	}
	REP(i,26)
		if(c1[i]&1){
			cout<<-1<<endl;
			return 0;
		}
	ll ans=0;
	int ss=0,ds=0;
	REP(i,n){
		if((++c2[str[i]])*2<=c1[str[i]]){
			src[ss++]=str[i];
			ans+=ds;
		}else{
			dst[ds++]=str[i];
		}
	}
	reverse(dst,dst+n/2);
	REP(i,n/2)
		g[src[i]].push(i);
	bit.Init(n/2);
	REP(i,n/2){
		int x=g[dst[i]].front();g[dst[i]].pop();
		ans+=x-i+bit.Get(x);
		bit.Add(0,1);
		bit.Add(x,-1);
	}
	cout<<ans<<endl;
}
```