output_description: If we cannot turn S into a palindrome, print `-1`. Otherwise, print the
  minimum required number of operations.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      S
attempt: from collections import Counter
  
  
  class fenwick_tree(object):
      def __init__(self, n):
          self.n = n
          self.data = [0] * n
  
      def __sum(self, r):
          s = 0
          while r > 0:
              s += self.data[r - 1]
              r -= r & -r
          return s
  
      def add(self, p, x):
          """a[p] += xを行う"""
          assert 0 <= p and p < self.n
          p += 1
          while p <= self.n:
              self.data[p - 1] += x
              p += p & -p
  
      def sum(self, l, r):
          """a[l] + a[l+1] + .. + a[r-1]を返す"""
          assert 0 <= l and l <= r and r <= self.n
          return self.__sum(r) - self.__sum(l)
  
  
  def calc_inversion(arr):
      N = len(arr)
      bit = fenwick_tree(N)
      atoi = {a: i for i, a in enumerate(arr)}
      res = 0
      for a in reversed(range(N)):
          i = atoi[a]
          res += bit.sum(0, i)
          bit.add(i, 1)
      return res
  
  
  def main():
      S = input()
      N = len(S)
      C = Counter(S)
  
      odd = 0
      mid = ""
      for k, v in C.items():
          if v & 1:
              odd += 1
              mid = k
  
      if N % 2 == 0:  # 偶数
          if odd:
              return -1
          ans = 0
          half = {k: v // 2 for k, v in C.items()}
          memo = {k: [] for k in C.keys()}
          cnt = 0
          bit = fenwick_tree(N)
          right = []
          for i, s in enumerate(S):
              if len(memo[s]) >= half[s]:  # 右
                  bit.add(i, 1)
                  right.append(s)
              else:  # 左
                  memo[s].append(cnt)
                  cnt += 1
                  ans += bit.sum(0, i)
          arr = []
          for s in right:
              arr.append(memo[s].pop())
          ans += calc_inversion(arr[::-1])
          return ans
  
      else:  # 奇数
          if odd != 1:
              return -1
          ans = 0
          half = {k: v // 2 for k, v in C.items()}
          memo = {k: [] for k in C.keys()}
          right = []
          cnt = 0
          LL = 0  # midより右にあるLの数
          RR = 0  # midより左にあるRの数
          seen = 0  # midが登場したか
  
          bit = fenwick_tree(N)
          for i, s in enumerate(S):
              if s == mid and len(memo[s]) == half[s]:
                  seen = 1
                  memo[s].append(cnt)
              elif len(memo[s]) >= half[s]:  # 右
                  bit.add(i, 1)
                  right.append(s)
                  if not seen:
                      RR += 1
              else:
                  memo[s].append(cnt)
                  cnt += 1
                  ans += bit.sum(0, i)
                  if seen:
                      LL += 1
          ans += abs(RR - LL)
          arr = []
          memo[mid].pop()
          for s in right:
              arr.append(memo[s].pop())
          ans += calc_inversion(arr[::-1])
          return ans
  
  
  print(main())
  
problem_description: Statement
  
  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.
samples: [{"input": "eel", "output": "1\n    \n\nWe can turn S into a palindrome by the following operation:\n\n  * Swap the 2-nd and 3-rd characters. S is now `ele`.\n\n* * *"}, {"input": "ataatmma", "output": "4\n    \n\nWe can turn S into a palindrome by the following operation:\n\n  * Swap the 5-th and 6-th characters. S is now `ataamtma`.\n  * Swap the 4-th and 5-th characters. S is now `atamatma`.\n  * Swap the 3-rd and 4-th characters. S is now `atmaatma`.\n  * Swap the 2-nd and 3-rd characters. S is now `amtaatma`.\n\n* * *"}, {"input": "snuke", "output": "-1\n    \n\nWe cannot turn S into a palindrome."}]