#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))

// mod
const ll MOD = 1000000007ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

// floating
typedef double Real;
const Real EPS = 1e-11;
#define EQ0(x) (abs(x)<EPS)
#define EQ(a,b) (abs(a-b)<EPS)
typedef complex<Real> P;

typedef struct Fenwick{
  int n;
  int *bit;
} Fenwick;
Fenwick *new_Fenwick(int n){
  Fenwick *ret = (Fenwick*)malloc(sizeof(Fenwick));
  ret->n = n;
  ret->bit = (int*)malloc(sizeof(int)*(n+1));
  memset(ret->bit,0,sizeof(int)*(n+1));
  return ret;
}
void free_Fenwick(Fenwick *f){
  free(f->bit);
  free(f);
}
void add_FW(Fenwick *f,int a,int w){
  int x;
  for(x=a;x<=f->n;x+=x&-x)f->bit[x]+=w;
}
int sum_FW(Fenwick *f,int a){
  int ret = 0;
  int x;
  for(x=a;x>0;x-=x&-x)ret+=f->bit[x];
  return ret;
}
int lower_bound_FW(Fenwick *f,int w){
  int x=0;
  int k=1;
  if(w<=0)return 0;
  while((k<<1)<=f->n)k<<=1;
  for(;k>0;k>>=1){
    if(x+k<=f->n && f->bit[x+k]<w){
      w-=f->bit[x+k];
      x+=k;
    }
  }
  return x+1;
}

int cnt[26];
int tmp[26];
int po[525252];
vi ord[26];
int tail[26];

int main(){
  string s;
  cin>>s;
  int n = s.size();
  // ?????§??????
  REP(i,n)cnt[s[i]-'a']++;
  REP(i,26)if(cnt[i]%2==1){
    puts("-1");
    return 0;
  }
  // ?????????
  ll yose = 0;
  int c1 = 0;
  string t;
  REP(i,n){
    int c = s[i]-'a';
    tmp[c]++;
    if(tmp[c]>cnt[c]/2){
      po[i]=1;
      c1 += 1;
    }else{
      po[i]=0;
      t += s[i];
      yose += c1;
    }
  }
  REP(i,n)if(po[i])t+=s[i];
  n = n/2;
  string a = t.substr(0,n);
  string b = t.substr(n);
  reverse(ALL(b));
  REP(i,n){
    int c = a[i]-'a';
    ord[c].push_back(i+1);
  }
  Fenwick *f = new_Fenwick(n+30);
  ll ans = 0;
  REP(i,n){
    int c = b[i]-'a';
    int x = ord[c][tail[c]++];
    ans += sum_FW(f,n+30) - sum_FW(f,x);
    add_FW(f,x,1);
  }
  printf("%lld\n",ans+yose);
  return 0;
}
### Prompt

In cpp, your task is to solve 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>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))

// mod
const ll MOD = 1000000007ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

// floating
typedef double Real;
const Real EPS = 1e-11;
#define EQ0(x) (abs(x)<EPS)
#define EQ(a,b) (abs(a-b)<EPS)
typedef complex<Real> P;

typedef struct Fenwick{
  int n;
  int *bit;
} Fenwick;
Fenwick *new_Fenwick(int n){
  Fenwick *ret = (Fenwick*)malloc(sizeof(Fenwick));
  ret->n = n;
  ret->bit = (int*)malloc(sizeof(int)*(n+1));
  memset(ret->bit,0,sizeof(int)*(n+1));
  return ret;
}
void free_Fenwick(Fenwick *f){
  free(f->bit);
  free(f);
}
void add_FW(Fenwick *f,int a,int w){
  int x;
  for(x=a;x<=f->n;x+=x&-x)f->bit[x]+=w;
}
int sum_FW(Fenwick *f,int a){
  int ret = 0;
  int x;
  for(x=a;x>0;x-=x&-x)ret+=f->bit[x];
  return ret;
}
int lower_bound_FW(Fenwick *f,int w){
  int x=0;
  int k=1;
  if(w<=0)return 0;
  while((k<<1)<=f->n)k<<=1;
  for(;k>0;k>>=1){
    if(x+k<=f->n && f->bit[x+k]<w){
      w-=f->bit[x+k];
      x+=k;
    }
  }
  return x+1;
}

int cnt[26];
int tmp[26];
int po[525252];
vi ord[26];
int tail[26];

int main(){
  string s;
  cin>>s;
  int n = s.size();
  // ?????§??????
  REP(i,n)cnt[s[i]-'a']++;
  REP(i,26)if(cnt[i]%2==1){
    puts("-1");
    return 0;
  }
  // ?????????
  ll yose = 0;
  int c1 = 0;
  string t;
  REP(i,n){
    int c = s[i]-'a';
    tmp[c]++;
    if(tmp[c]>cnt[c]/2){
      po[i]=1;
      c1 += 1;
    }else{
      po[i]=0;
      t += s[i];
      yose += c1;
    }
  }
  REP(i,n)if(po[i])t+=s[i];
  n = n/2;
  string a = t.substr(0,n);
  string b = t.substr(n);
  reverse(ALL(b));
  REP(i,n){
    int c = a[i]-'a';
    ord[c].push_back(i+1);
  }
  Fenwick *f = new_Fenwick(n+30);
  ll ans = 0;
  REP(i,n){
    int c = b[i]-'a';
    int x = ord[c][tail[c]++];
    ans += sum_FW(f,n+30) - sum_FW(f,x);
    add_FW(f,x,1);
  }
  printf("%lld\n",ans+yose);
  return 0;
}
```