#include<bits/stdc++.h>
using namespace std;
using Int = long long;


template<typename T> 
struct BIT{
  Int n;
  vector<T> bit;
  //1-indexed
  BIT():n(-1){}
  BIT(Int n_,T d):n(n_),bit(n_+1,d){}
  
  T sum(Int i){
    T s=0;
    for(Int x=i;x>0;x-=(x&-x))
      s+=bit[x];
    return s;
  }
  void add(Int i,T a){
    if(i==0) return;
    for(Int x=i;x<=n;x+=(x&-x))
      bit[x]+=a;
  }
  
  Int lower_bound(Int w){
    if(w<=0) return 0;
    Int x=0,r=1;
    while(r<n) r<<=1;
    for(Int k=r;k>0;k>>=1){
      if(x+k<=n&&bit[x+k]<w){
	w-=bit[x+k];
	x+=k;
      }
    }
    return x+1;
  }
  
  T sum0(Int i){
    return sum(i+1);
  }
  void add0(Int i,T a){
    add(i+1,a);
  }
};

signed main(){
  string s;
  cin>>s;
  Int n=s.size();
  {
    vector<Int> c(26,0);
    for(Int i=0;i<n;i++) c[s[i]-'a']++;
    Int x=0;
    for(Int i=0;i<26;i++) if(c[i]&1) x++;
    if(x>1){
      cout<<-1<<endl;
      return 0;
    }
  }

  vector<deque<Int> > x(26);
  for(Int i=0;i<n;i++) x[s[i]-'a'].push_back(i);


  BIT<Int> bit(n+1000,0);
  
  Int ans=0;
  Int cnt=0,pos=-1;
  vector<Int> used(n,0);
  for(Int i=0;i<n;i++){
    if(used[i]) continue;
    Int c=s[i]-'a';
    if(x[c].size()==1u){
      pos=cnt++;
      bit.add0(i,1);
      continue;
    }
    Int a=x[c].front(),b=x[c].back();
    assert(a==i);
    x[c].pop_front();x[c].pop_back();
    used[b]=1;
    //cout<<n-(cnt+1)<<" "<<(b-bit.sum0(b))<<endl;
    ans+=(n-(cnt+1))-(b-bit.sum0(b));
    bit.add0(b,1);
    cnt++;
  }
  //cout<<pos<<endl;
  if(~pos) ans+=(n/2-pos);
  cout<<ans<<endl;
  return 0;
}
### Prompt

Please create a solution in cpp 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>
using namespace std;
using Int = long long;


template<typename T> 
struct BIT{
  Int n;
  vector<T> bit;
  //1-indexed
  BIT():n(-1){}
  BIT(Int n_,T d):n(n_),bit(n_+1,d){}
  
  T sum(Int i){
    T s=0;
    for(Int x=i;x>0;x-=(x&-x))
      s+=bit[x];
    return s;
  }
  void add(Int i,T a){
    if(i==0) return;
    for(Int x=i;x<=n;x+=(x&-x))
      bit[x]+=a;
  }
  
  Int lower_bound(Int w){
    if(w<=0) return 0;
    Int x=0,r=1;
    while(r<n) r<<=1;
    for(Int k=r;k>0;k>>=1){
      if(x+k<=n&&bit[x+k]<w){
	w-=bit[x+k];
	x+=k;
      }
    }
    return x+1;
  }
  
  T sum0(Int i){
    return sum(i+1);
  }
  void add0(Int i,T a){
    add(i+1,a);
  }
};

signed main(){
  string s;
  cin>>s;
  Int n=s.size();
  {
    vector<Int> c(26,0);
    for(Int i=0;i<n;i++) c[s[i]-'a']++;
    Int x=0;
    for(Int i=0;i<26;i++) if(c[i]&1) x++;
    if(x>1){
      cout<<-1<<endl;
      return 0;
    }
  }

  vector<deque<Int> > x(26);
  for(Int i=0;i<n;i++) x[s[i]-'a'].push_back(i);


  BIT<Int> bit(n+1000,0);
  
  Int ans=0;
  Int cnt=0,pos=-1;
  vector<Int> used(n,0);
  for(Int i=0;i<n;i++){
    if(used[i]) continue;
    Int c=s[i]-'a';
    if(x[c].size()==1u){
      pos=cnt++;
      bit.add0(i,1);
      continue;
    }
    Int a=x[c].front(),b=x[c].back();
    assert(a==i);
    x[c].pop_front();x[c].pop_back();
    used[b]=1;
    //cout<<n-(cnt+1)<<" "<<(b-bit.sum0(b))<<endl;
    ans+=(n-(cnt+1))-(b-bit.sum0(b));
    bit.add0(b,1);
    cnt++;
  }
  //cout<<pos<<endl;
  if(~pos) ans+=(n/2-pos);
  cout<<ans<<endl;
  return 0;
}
```