#include <iostream>
#include <vector>
#include <deque>

using int64 = long long;

template<class T>
using vec = std::vector<T>;

class BIT {
  public:
    int n;
    vec<int> bit;
    
    BIT(int N)
    {
        n = N + 1;
        bit.assign(n, 0);
    }

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

int64 solve(const std::string &S)
{
    int N = S.size();
    std::deque<int> pos[26];
    for (int i = 0; i < N; i++) {
        pos[S[i] - 'a'].emplace_back(i); 
    }
    
    for (int i = 0; i < 26; i++) {
        if (pos[i].size() & 1) {
            return -1;
        }
    }
    
    int64 res = 0;
    vec<bool> used(N);
    BIT b(2 * N);
    for (int i = 0; i < N; i++) {
        b.add(i + 1, +1);
    }
    
    for (int i = 0; i < N; i++) {        
        int v = S[i] - 'a';       
        if (used[i]) continue;
        
        int pb = pos[v].back();
        pos[v].pop_front(); used[pb] = 1;        
        res += b.sum(2 * N - i) - b.sum(pb + 1);
        b.add(pb + 1, -1);
        b.add(2 * N - i, +1);
        pos[v].pop_back();
    }
    return res;
}

int main()
{
    std::string S;
    std::cin >> S;
    std::cout << solve(S) << std::endl;
    return 0;
}
### Prompt

Develop a solution in Cpp to the problem described below:

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 <vector>
#include <deque>

using int64 = long long;

template<class T>
using vec = std::vector<T>;

class BIT {
  public:
    int n;
    vec<int> bit;
    
    BIT(int N)
    {
        n = N + 1;
        bit.assign(n, 0);
    }

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

int64 solve(const std::string &S)
{
    int N = S.size();
    std::deque<int> pos[26];
    for (int i = 0; i < N; i++) {
        pos[S[i] - 'a'].emplace_back(i); 
    }
    
    for (int i = 0; i < 26; i++) {
        if (pos[i].size() & 1) {
            return -1;
        }
    }
    
    int64 res = 0;
    vec<bool> used(N);
    BIT b(2 * N);
    for (int i = 0; i < N; i++) {
        b.add(i + 1, +1);
    }
    
    for (int i = 0; i < N; i++) {        
        int v = S[i] - 'a';       
        if (used[i]) continue;
        
        int pb = pos[v].back();
        pos[v].pop_front(); used[pb] = 1;        
        res += b.sum(2 * N - i) - b.sum(pb + 1);
        b.add(pb + 1, -1);
        b.add(2 * N - i, +1);
        pos[v].pop_back();
    }
    return res;
}

int main()
{
    std::string S;
    std::cin >> S;
    std::cout << solve(S) << std::endl;
    return 0;
}
```