/*  -*- coding: utf-8 -*-
 *
 * 1596.cc: Char Swap
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_N = 400000;
const int MAX_H = MAX_N / 2;

/* typedef */

typedef long long ll;

/* global variables */

char s[MAX_N + 4];
int cns[26], cas[26][MAX_H], cis[26], cjs[26];
int ds[MAX_H], ts[MAX_H];

/* subroutines */

ll merge_sort(int as[], int tmp[], int l, int r) { // [l, r)
  ll ic = 0;

  if (l + 1 < r) {
    int m = (l + r) / 2;
  
    ic = merge_sort(as, tmp, l, m) + merge_sort(as, tmp, m, r);

    int i = l, j = m, k = l;

    while (i < m && j < r) {
      if (as[i] <= as[j]) tmp[k++] = as[i++];
      else tmp[k++] = as[j++], ic += m - i;
    }

    while (i < m) tmp[k++] = as[i++];
    while (j < r) tmp[k++] = as[j++];

    for (int i = l; i < r; i++) as[i] = tmp[i];
  }  

  return ic;
}

/* main */

int main() {
  scanf("%s", s);

  int n = 0;
  for (; s[n]; n++) cns[s[n] - 'a']++;

  for (int i = 0; i < 26; i++) {
    if (cns[i] & 1) {
      puts("-1");
      return 0;
    }
    cns[i] >>= 1;
  }

  ll sum = 0;
  for (int i = 0, k = 0, d = 0; i < n; i++) {
    int c = s[i] - 'a';
    if (cis[c] < cns[c]) {
      cas[c][cis[c]++] = k++;
      sum += d;
    }
    else
      d++;
  }

  for (int i = n - 1, j = 0; i >= 0; i--) {
    int c = s[i] - 'a';
    if (cjs[c] < cns[c]) ds[j++] = cas[c][cjs[c]++];
  }

  int h = n / 2;
  //for (int i = 0; i < h; i++) printf("%d ", ds[i]); putchar('\n');

  sum += merge_sort(ds, ts, 0, h);
  printf("%lld\n", sum);
  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
/*  -*- coding: utf-8 -*-
 *
 * 1596.cc: Char Swap
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_N = 400000;
const int MAX_H = MAX_N / 2;

/* typedef */

typedef long long ll;

/* global variables */

char s[MAX_N + 4];
int cns[26], cas[26][MAX_H], cis[26], cjs[26];
int ds[MAX_H], ts[MAX_H];

/* subroutines */

ll merge_sort(int as[], int tmp[], int l, int r) { // [l, r)
  ll ic = 0;

  if (l + 1 < r) {
    int m = (l + r) / 2;
  
    ic = merge_sort(as, tmp, l, m) + merge_sort(as, tmp, m, r);

    int i = l, j = m, k = l;

    while (i < m && j < r) {
      if (as[i] <= as[j]) tmp[k++] = as[i++];
      else tmp[k++] = as[j++], ic += m - i;
    }

    while (i < m) tmp[k++] = as[i++];
    while (j < r) tmp[k++] = as[j++];

    for (int i = l; i < r; i++) as[i] = tmp[i];
  }  

  return ic;
}

/* main */

int main() {
  scanf("%s", s);

  int n = 0;
  for (; s[n]; n++) cns[s[n] - 'a']++;

  for (int i = 0; i < 26; i++) {
    if (cns[i] & 1) {
      puts("-1");
      return 0;
    }
    cns[i] >>= 1;
  }

  ll sum = 0;
  for (int i = 0, k = 0, d = 0; i < n; i++) {
    int c = s[i] - 'a';
    if (cis[c] < cns[c]) {
      cas[c][cis[c]++] = k++;
      sum += d;
    }
    else
      d++;
  }

  for (int i = n - 1, j = 0; i >= 0; i--) {
    int c = s[i] - 'a';
    if (cjs[c] < cns[c]) ds[j++] = cas[c][cjs[c]++];
  }

  int h = n / 2;
  //for (int i = 0; i < h; i++) printf("%d ", ds[i]); putchar('\n');

  sum += merge_sort(ds, ts, 0, h);
  printf("%lld\n", sum);
  return 0;
}


```