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
S = input()
N = len(S)
ctr = Counter(S)
if len([1 for v in ctr.values() if v%2]) > 1:
    print(-1)
    exit()

M = None
for k,v in ctr.items():
    if v%2:
        M = k
    ctr[k] //= 2

def ctoi(c):
    return ord(c) - ord('a')
from collections import deque
idxs = [deque() for _ in range(26)]
for i,c in enumerate(S):
    idxs[ctoi(c)].append(i)

A = ''
P = []
i = 0
while len(A) < N//2:
    c = S[i]
    if ctr[c] > 0:
        ctr[c] -= 1
        A += c
        P.append(idxs[ctoi(c)].popleft())
    i += 1
if M:
    P.append(idxs[ctoi(M)].popleft())
for c in A[::-1]:
    P.append(idxs[ctoi(c)].popleft())

def inversion(inds):
    bit = [0] * (N+1)
    def bit_add(x,w):
        while x <= N:
            bit[x] += w
            x += (x & -x)
    def bit_sum(x):
        ret = 0
        while x > 0:
            ret += bit[x]
            x -= (x & -x)
        return ret
    inv = 0
    for ind in reversed(inds):
        inv += bit_sum(ind + 1)
        bit_add(ind + 1, 1)
    return inv

print(inversion(P))