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
from collections import Counter
from sys import exit
class BIT:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

S = input()
N = len(S)

cnt = 0
SC = Counter(S)
for v in SC.values():
    if v % 2:
        cnt += 1
if cnt > 1:
    print(-1)
    exit()

geta = 10**9+7
T = [None]*N
table = Counter()
idx = dict()
ctr = 0
for i, s in enumerate(S):
    table[s] += 1
    if table[s] <= SC[s]//2: 
        T[i] = ctr
        idx[ord(s)*geta + table[s]] = ctr
        ctr += 1
        continue
    if table[s] > (1+SC[s])//2:
        T[i] = N - 1 - idx[ord(s)*geta+(SC[s] + 1 - table[s])]
        continue
    if SC[s] % 2 and table[s] == (SC[s]+1)//2:
        T[i] = (N-1)//2
        continue
Tr = [None]*N
for i, v in enumerate(T):
    Tr[v] = i
B = BIT(N)
ans = 0
for tr in Tr[::-1]:
    ans += B.sum(tr + 1)
    B.add(tr + 1, 1)
print(ans)