#include <iostream>
#include <queue>
#include <vector>

using namespace std;
using ll = long long;

#define REP(i, n) for (int i = 0; i < n; ++i)

class FenwickTree {
public:
  FenwickTree(int _n) : n(_n) { v.resize(_n + 1, 0); }

  void add(int pos, long long val) {
    pos++;
    for (int i = pos; i <= n; i += i & (-i))
      v[i] += val;
  }

  // sum [l, r]
  long long sum(int l, int r) { return sum(r) - sum(l - 1); }

  // sum [0,pos]
  long long sum(int pos) {
    pos++;
    long long ret = 0;
    for (int i = pos; i > 0; i -= i & (-i))
      ret += v[i];
    return ret;
  }

private:
  int n;
  std::vector<long long> v;
};

int main() {
  string s;
  cin >> s;
  int n = s.size();
  vector<int> cnt(26);
  REP(i, n) cnt[s[i] - 'a']++;
  REP(i, 26) {
    if (cnt[i] % 2 == 1) {
      cout << -1 << endl;
      return 0;
    }
  }
  vector<int> l, r;
  vector<int> cnt2(26, 0);
  REP(i, n) {
    if (cnt2[s[i] - 'a'] < cnt[s[i] - 'a'] / 2) {
      l.push_back(i);
    } else {
      r.push_back(i);
    }
    cnt2[s[i] - 'a']++;
  }

  ll ans = 0;
  REP(i, n / 2) { ans += l[i] - i; }
  vector<vector<int>> pos(26);
  REP(i, n / 2) { pos[s[l[i]] - 'a'].push_back(i); }
  FenwickTree bit(n / 2);
  vector<int> ind(26);
  REP(i, n / 2) {
    char c = s[r[n / 2 - 1 - i]];
    int p = pos[c - 'a'][ind[c - 'a']];
    ind[c - 'a']++;
    ans += -bit.sum(p) + p;
    bit.add(p, 1);
  }
  cout << ans << endl;
}

### Prompt

Your task is to create 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 <iostream>
#include <queue>
#include <vector>

using namespace std;
using ll = long long;

#define REP(i, n) for (int i = 0; i < n; ++i)

class FenwickTree {
public:
  FenwickTree(int _n) : n(_n) { v.resize(_n + 1, 0); }

  void add(int pos, long long val) {
    pos++;
    for (int i = pos; i <= n; i += i & (-i))
      v[i] += val;
  }

  // sum [l, r]
  long long sum(int l, int r) { return sum(r) - sum(l - 1); }

  // sum [0,pos]
  long long sum(int pos) {
    pos++;
    long long ret = 0;
    for (int i = pos; i > 0; i -= i & (-i))
      ret += v[i];
    return ret;
  }

private:
  int n;
  std::vector<long long> v;
};

int main() {
  string s;
  cin >> s;
  int n = s.size();
  vector<int> cnt(26);
  REP(i, n) cnt[s[i] - 'a']++;
  REP(i, 26) {
    if (cnt[i] % 2 == 1) {
      cout << -1 << endl;
      return 0;
    }
  }
  vector<int> l, r;
  vector<int> cnt2(26, 0);
  REP(i, n) {
    if (cnt2[s[i] - 'a'] < cnt[s[i] - 'a'] / 2) {
      l.push_back(i);
    } else {
      r.push_back(i);
    }
    cnt2[s[i] - 'a']++;
  }

  ll ans = 0;
  REP(i, n / 2) { ans += l[i] - i; }
  vector<vector<int>> pos(26);
  REP(i, n / 2) { pos[s[l[i]] - 'a'].push_back(i); }
  FenwickTree bit(n / 2);
  vector<int> ind(26);
  REP(i, n / 2) {
    char c = s[r[n / 2 - 1 - i]];
    int p = pos[c - 'a'][ind[c - 'a']];
    ind[c - 'a']++;
    ans += -bit.sum(p) + p;
    bit.add(p, 1);
  }
  cout << ans << endl;
}

```