#include <bits/stdc++.h>
#define N (1<<20)
using namespace std;
typedef long long ll;
string str;
int bit[N+1],n;
int a[N];

int sum(int i){
  int res=0;
  while(i>0){
    res+=bit[i];
    i-=i&-i;
  }
  return res;
}

void add(int i,int x){
  while(i<=n){
    bit[i]+=x;
    i+=i&-i;
  }
}

ll solve(){
  n=str.size();
  int cnt[30]={},cnt2[30]={};
  for(int i=0;i<n;i++)cnt[str[i]-'a']++;
  for(int i=0;i<30;i++)if(cnt[i]%2)return -1;
  
  int A=0;
  stack <int> stk[30];
  
  for(int i=0;i<n;i++){
    int idx=str[i]-'a';
    if(cnt[idx]/2>cnt2[idx]){
      stk[idx].push(A);
      A++;
      cnt2[idx]++;
      a[i]=A;
    }
    else {
      a[i]=n-stk[idx].top();
      stk[idx].pop();
    }
  }

  ll ans=0;
  for(int j=0;j<n;j++){
    ans+=j-sum(a[j]);
    add(a[j],1);
  }
  return ans;
}


int main(){
  cin>>str;
  reverse(str.begin(),str.end());
  cout <<solve()<<endl;  
  return 0;
}
### Prompt

Please formulate 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 N (1<<20)
using namespace std;
typedef long long ll;
string str;
int bit[N+1],n;
int a[N];

int sum(int i){
  int res=0;
  while(i>0){
    res+=bit[i];
    i-=i&-i;
  }
  return res;
}

void add(int i,int x){
  while(i<=n){
    bit[i]+=x;
    i+=i&-i;
  }
}

ll solve(){
  n=str.size();
  int cnt[30]={},cnt2[30]={};
  for(int i=0;i<n;i++)cnt[str[i]-'a']++;
  for(int i=0;i<30;i++)if(cnt[i]%2)return -1;
  
  int A=0;
  stack <int> stk[30];
  
  for(int i=0;i<n;i++){
    int idx=str[i]-'a';
    if(cnt[idx]/2>cnt2[idx]){
      stk[idx].push(A);
      A++;
      cnt2[idx]++;
      a[i]=A;
    }
    else {
      a[i]=n-stk[idx].top();
      stk[idx].pop();
    }
  }

  ll ans=0;
  for(int j=0;j<n;j++){
    ans+=j-sum(a[j]);
    add(a[j],1);
  }
  return ans;
}


int main(){
  cin>>str;
  reverse(str.begin(),str.end());
  cout <<solve()<<endl;  
  return 0;
}
```