You are given a string S consisting of lowercase English letters. Determine whether we can turn S into a palindrome by repeating the operation of swapping two adjacent characters. If it is possible, find the minimum required number of operations.

Constraints

* 1 \leq |S| \leq 2 × 10^5
* S consists of lowercase English letters.

Input

Input is given from Standard Input in the following format:


S


Output

If we cannot turn S into a palindrome, print `-1`. Otherwise, print the minimum required number of operations.

Examples

Input

eel


Output

1


Input

ataatmma


Output

4


Input

snuke


Output

-1
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 87;
string s;
deque<int> p[26];
int f[N];
void add(int i,int v)
{
    for (; i < N; i += i & -i)
        f[i] += v;
}
int qry(int i)
{
    int r = 0;
    for (; i; i ^= i & - i)
        r += f[i];
    return r;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> s;
    int n = s.size();
    for (int i = 0; i < n; ++i) {
        p[s[i]-'a'].push_back(i+1);
        add(i+1,1);
    }
    int mi = -1;
    for (int i = 0; i < 26; ++i)
        if (p[i].size() & 1) {
            if (mi != -1 || n % 2 == 0) {
                cout << "-1\n";
                return 0;
            }
            mi = i;
        }
    long long ans = 0;
    for (int i = 1, j = n; i < j; ++i, --j) {
        pair<int,int> best(INT_MAX,INT_MAX);
        for (int c = 0; c < 26; ++c) {
            if (p[c].size() > 1) {
                int l = qry(p[c].front()), r = qry(p[c].back());
                int w = l-1 + n-i*2+2-r;
                best = min(best, {w,c});
            }
        }
        ans += best.first;
        auto & q = p[best.second];
        add(q.front(),-1);
        add(q.back(),-1);
        q.pop_front();
        q.pop_back();
    }
    cout << ans << '\n';
}
