1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class BIT:
    def __init__(self, n):
        self.sums = [0] * (n+1)
    
    def update(self, i, delta):
        while i < len(self.sums):
            self.sums[i] += delta
            i += i & (-i)
    
    def query(self, i):
        res = 0
        while i > 0:
            res += self.sums[i]
            i -= i & (-i)
        return res

class Solution:
    def minMovesToMakePalindrome(self, s):
        n = len(s)
        s = [ord(x) - 95 for x in s]
        ans, bit = 0, BIT(n)

        idx = {}
        for i, c in enumerate(s):
            if c not in idx:
                idx[c] = [i]
            else:
                idx[c].append(i)

        odd = 0
        for i in idx:
            if len(idx[i])%2 != 0:
                odd += 1
        if odd > 1:
            return -1

        B, P = [0] * n, []
        for c, I in idx.items():
            cnt = len(I)
            if cnt % 2:
                B[I[cnt//2]] = n//2 + 1
            for i in range((cnt)//2):
                P += [(I[i], I[~i])]

        for i, (l, r) in enumerate(sorted(P)):
            B[l], B[r] = i + 1, n - i
        
        for i, b in enumerate(B):
            ans += i - bit.query(b)
            bit.update(b, 1)
        
        return ans
print(Solution().minMovesToMakePalindrome(input()))