#include<bits/stdc++.h>
#define reps(X,O,Y) for(int X=O;X<(Y);++X)
#define rep(X,Y) reps(X,0,Y)
#define rreps(X,O,Y) for(int X=(Y)-1;X>=(O);--X)
#define rrep(X,Y) rreps(X,0,Y)
#define all(X) begin(X),end(X)
#define X first
#define Y second
#define pb push_back

using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll INF=1e12;

const int nn=512345;
ll bit[nn];
void add(int i,ll val){
  ++i;
  while(i<nn){
    bit[i]+=val;
    i+=i&-i;
  }
  return;
}
ll sum(int i){
  ++i;
  ll s=0;
  while(i>0){
    s+=bit[i];
    i-=i&-i;
  }
  return s;
}

int main(){
  string str;
  cin>>str;
  int n=str.size();
  vector<int> cnt(200);
  for(char c:str) ++cnt[c];
  ll re=0;
  char center=0;
  reps(c,'a','z'+1) if(cnt[c]%2){
    if(center){
      cout<<-1<<endl;
      return 0;
    }
    center=c;
    pll mn(INF,INF);
    rep(i,n) if(str[i]==center) mn=min(mn,pll(abs(i-n/2),i));
    re=mn.X;
    str.erase(mn.Y,1); --n; --cnt[c];
  }
  vector<int> usd(200);
  string a,b;
  rep(i,n){
    if(usd[str[i]]<cnt[str[i]]/2){
      a+=str[i];
      re+=i;
      ++usd[str[i]];
    }else{
      b+=str[i];
    }
  }
  rep(i,n/2) re-=i;
  reverse(all(b));
  //cout<<a<<","<<b<<":"<<re<<endl;
  
  vector<int> r[200];
  rep(i,n/2){
    r[b[i]].pb(i);
  }
  rep(i,200) reverse(all(r[i]));
  rep(i,n/2){
    assert(r[a[i]].size());
    int x=r[a[i]].back();
    r[a[i]].pop_back();
    re+=x-sum(x);
    add(x,1);
  }
  cout<<re<<endl;
  return 0;
}
### Prompt

Generate 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 reps(X,O,Y) for(int X=O;X<(Y);++X)
#define rep(X,Y) reps(X,0,Y)
#define rreps(X,O,Y) for(int X=(Y)-1;X>=(O);--X)
#define rrep(X,Y) rreps(X,0,Y)
#define all(X) begin(X),end(X)
#define X first
#define Y second
#define pb push_back

using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll INF=1e12;

const int nn=512345;
ll bit[nn];
void add(int i,ll val){
  ++i;
  while(i<nn){
    bit[i]+=val;
    i+=i&-i;
  }
  return;
}
ll sum(int i){
  ++i;
  ll s=0;
  while(i>0){
    s+=bit[i];
    i-=i&-i;
  }
  return s;
}

int main(){
  string str;
  cin>>str;
  int n=str.size();
  vector<int> cnt(200);
  for(char c:str) ++cnt[c];
  ll re=0;
  char center=0;
  reps(c,'a','z'+1) if(cnt[c]%2){
    if(center){
      cout<<-1<<endl;
      return 0;
    }
    center=c;
    pll mn(INF,INF);
    rep(i,n) if(str[i]==center) mn=min(mn,pll(abs(i-n/2),i));
    re=mn.X;
    str.erase(mn.Y,1); --n; --cnt[c];
  }
  vector<int> usd(200);
  string a,b;
  rep(i,n){
    if(usd[str[i]]<cnt[str[i]]/2){
      a+=str[i];
      re+=i;
      ++usd[str[i]];
    }else{
      b+=str[i];
    }
  }
  rep(i,n/2) re-=i;
  reverse(all(b));
  //cout<<a<<","<<b<<":"<<re<<endl;
  
  vector<int> r[200];
  rep(i,n/2){
    r[b[i]].pb(i);
  }
  rep(i,200) reverse(all(r[i]));
  rep(i,n/2){
    assert(r[a[i]].size());
    int x=r[a[i]].back();
    r[a[i]].pop_back();
    re+=x-sum(x);
    add(x,1);
  }
  cout<<re<<endl;
  return 0;
}
```