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.

-----Sample Input-----
eel

-----Sample Output-----
1

We can turn S into a palindrome by the following operation:
 - Swap the 2-nd and 3-rd characters. S is now ele.

Difficulty: competition

Starter code:

Solutions:
import collections


class Bit():
    def __init__(self, l):
        self.size = l
        self.bit = [0] * (self.size+1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.bit[i] += x
            i += i & -i

    def __str__(self):
        return str(self.bit)


S = str(input())
N = len(S)
index = collections.defaultdict(list)

for i, c in enumerate(S):
    index[c].append(i)

ctr = N // 2
B = [0] * N
flag = 0
P = []

for c, k in list(index.items()):
    cnt = len(k)
    if cnt % 2:
        if flag == 1:
            print((-1))
            return
        flag = 1
        B[k[cnt // 2]] = ctr + 1
    for i in range(cnt // 2):
        l, r = k[i], k[-(i+1)]
        P.append((l, r))

P.sort()

for i, (l, r) in enumerate(P):
    B[l], B[r] = i + 1, N - i

ans = 0
bit = Bit(N)
for i, b in enumerate(B):
    ans += i - bit.sum(b)
    bit.add(b, 1)

print(ans)


"""
まず、奇数個存在する文字種が複数ある場合は、回文にできない。
それ以外の場合は、回文にできる。
次に、操作の最小回数は、回文になった場合の各文字のインデックスを求めておき、BITを使って、入れ替えが必要な回数を求めて置く
"""
from collections import Counter
S = input()
N = len(S)
#各文字の出現回数をカウント
apperance = Counter(S)

#回文を作成できるか判定
flag = False
for k,v in list(apperance.items()):
    if v%2==1:
        if flag:
            print((-1))
            return
        else:
            flag = True
            t = k


#place[s] -> 文字sの出現位置
place = {}
for i in range(N):
    s = S[i]
    if s not in place:
        place[s] = []
    place[s].append(i)

#memo[i] -> Sのi文字目の回文上でのインデックス
memo = [-1] *(N)

#回文前半、後半に含まれることになる文字に、回文上でのインデックスを割り当てる。
tmp = 0
tmpApperance = {}
for i in range(N):
    s = S[i]
    if s not in tmpApperance:
        tmpApperance[s] = 1
    else:
        tmpApperance[s] += 1
    if tmpApperance[s] <= apperance[s]//2:
        memo[i] = tmp
        backIdx = place[s][-tmpApperance[s]]
        memo[backIdx] = N-tmp-1
        tmp += 1


#回文の真ん中に含まれることになる文字に、回文上でのインデックスを割り当てる。
if flag:
    idx = N//2
    memo[place[t][len(place[t])//2]] = idx

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
bit = BIT(N)
cnt = 0
for i in range(N):
    m = memo[i]+1
    bit.add(m,1)
    cnt += bit.sum(N)-bit.sum(m)

print(cnt)


from collections import Counter

class BIT:
    def __init__(self,n):
        self.tree = [0]*(n+1)
        self.size = n
    
    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)
count = Counter(S)
flag = False
for v in list(count.values()):
    if v%2 == 1:
        if flag:
            print((-1))
            return
        else:
            flag = True


"""
文字sのi文字目がどこにあるか、をO(1)で取り出せる辞書が必要
"""
placeAtS = {s:[] for s in list(set(S))}
for i in range(N):
    s = S[i]
    placeAtS[s].append(i)

count2 = {s:0 for s in list(set(S))}

placeAtT = [None]*(N)
tmp = 0
for i in range(N):
    s = S[i]
    count2[s] += 1
    if count2[s] <= count[s]//2:
        placeAtT[i] = tmp
        mirror = placeAtS[s][count[s]-count2[s]]
        placeAtT[mirror] = N - tmp - 1
        tmp += 1

for i in range(N):
    if placeAtT[i] == None:
        placeAtT[i] = tmp

bit = BIT(N)
ans = 0
for i in range(N):
    bit.add(placeAtT[i]+1,1)
    ans += bit.sum(N) - bit.sum(placeAtT[i]+1)

print(ans)


import sys
input = sys.stdin.readline
from collections import deque, defaultdict, Counter

S = input().rstrip()
L = len(S)

c = Counter(S)
if sum((x&1 for x in c.values())) >= 2:
    print(-1)
    return

alphabet_to_pos = defaultdict(deque)

for i,x in enumerate(S,1):
    alphabet_to_pos[x].append(i)

after = [None] * len(S)
n = 0
for i,x in enumerate(S,1):
    p = alphabet_to_pos[x]
    if not p:
        continue
    if len(p) == 1:
        p.pop()
        after[L//2] = i
        continue
    p.popleft()
    j = p.pop()
    after[n] = i
    after[L - n - 1] = j
    n += 1

def BIT_update(tree,x):
    while x <= L:
        tree[x] += 1
        x += x & (-x)

def BIT_sum(tree,x):
    s = 0
    while x:
        s += tree[x]
        x -= x & (-x)
    return s

answer = 0
tree = [0] * (L+1)
for i,x in enumerate(after):
    answer += i - BIT_sum(tree,x)
    BIT_update(tree,x)

print(answer)

S=list(input())
N=len(S)
ord_A=ord("a")
alp=[0]*26
odd=-1
for i in range(N):
  m=ord(S[i])-ord_A
  alp[m]+=1
for k in range(26):
  if alp[k]%2==1:
    if odd==-1:
      odd=k
    else:
      print(-1)
      return
pos=[[] for i in range(26)]
Sequence=[0]*N
d=0
alp_num=[0]*26
for i in range(N):
  m=ord(S[i])-ord_A
  alp_num[m]+=1
  if 2*alp_num[m]<=alp[m]:
    Sequence[i]=d
    pos[m].append(d)
    d+=1
  elif m==odd and alp_num[m]==alp[m]//2+1:
    Sequence[i]=N//2
  else:
    j=pos[m].pop()
    Sequence[i]=N-1-j

def add(B,a,n):
    x = a
    while x<=n:
        B[x]+=1
        x+=x&(-x)
        
def sums(B,a):
    x=a
    S=0
    while x!=0:
        S+=B[x]
        x-=x&(-x)
    return S
  
def invnumber(n,A):
  B=[0]*(n*2+1)
  invs=0
  for i in range(n):
      s=A[i]+n
      invs+=sums(B,s)
      add(B,s,n*2)
  return n*(n-1)//2-invs

print(invnumber(N,Sequence))

import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

class BitSum:
    def __init__(self, n):
        self.n = n + 3
        self.table = [0] * (self.n + 1)

    def update(self, i, x):
        i += 1
        while i <= self.n:
            self.table[i] += x
            i += i & -i

    def sum(self, i):
        i += 1
        res = 0
        while i > 0:
            res += self.table[i]
            i -= i & -i
        return res

def InversionNumber(lst):
    bit = BitSum(max(lst))
    res = 0
    for i, a in enumerate(lst):
        res += i - bit.sum(a)
        bit.update(a, 1)
    return res

def main():
    s = input()
    n = len(s)
    ord_a = ord("a")
    cnts = [0] * 26
    s_code = []
    flag_odd = False
    for c in s:
        code = ord(c) - ord_a
        s_code.append(code)
        cnts[code] += 1
    odd_code = -1
    for code, cnt in enumerate(cnts):
        if cnt % 2 == 1:
            if flag_odd:
                print(-1)
                return
            else:
                odd_code = code
                flag_odd = True
        cnts[code] = cnt // 2
    tois = [[] for _ in range(26)]
    to_sort_idx = []
    new_idx = 1
    for code in s_code:
        if cnts[code] > 0:
            to_sort_idx.append(new_idx)
            tois[code].append(n + 1 - new_idx)
            cnts[code] -= 1
            new_idx += 1
        else:
            if flag_odd and code == odd_code:
                to_sort_idx.append(n // 2 + 1)
                flag_odd = False
            else:
                to_sort_idx.append(tois[code].pop())
    # print(to_sort_idx)
    print(InversionNumber(to_sort_idx))

main()


from collections import deque
import copy
class BIT:
    def __init__(self, node_size):
        self._node = node_size+1
        self.bit = [0]*self._node
 
    def add(self, index, add_val):
        while index < self._node:
            self.bit[index] += add_val
            index += index & -index
 
    def sum(self, index):
        res = 0
        while index > 0:
            res += self.bit[index]
            index -= index & -index
        return res
 
s = input()
n = len(s)
a = [ord(i) - ord("a") for i in s]
x = [0]*26
for i in a:
  x[i] += 1
flag = 1
ki = -1
for i in x:
  if i%2 == 1:
    if flag:
      flag = 0
    else:
      print(-1)
      return
c = []
x2 = [0]*26
for i in a:
  x2[i] += 1
  if x[i]//2 >= x2[i]:
    c.append(i)
for i in range(26):
  if x[i]%2 == 1:
    b = copy.deepcopy(c)
    c.append(i)
    b = b[::-1]
    c.extend(b)
    break
else:
  b = copy.deepcopy(c)
  b = b[::-1]
  c.extend(b) 
d = {}
for i in range(26):
  d[i] = deque([])
for i in range(n):
  d[c[i]].append(i+1)
for i in range(n):
  x = d[a[i]].popleft()
  a[i] = x
b = []
for i in range(n):
  b.append([a[i],i+1])
b.sort()
b = b[::-1]
bit = BIT(n)
ans = 0
for i,j in b:
  bit.add(j,1)
  ans += bit.sum(j-1)
print(ans)

"""
回文の左半分の文字列たちを操作する。
左半分の各文字に対して、本来あるべき場所(Index)を定義する。
あとは、左半分の文字

"""

from collections import Counter
class BIT:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):  # 1-index
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):  # 1-index
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

S = input()
N = len(S)
count = Counter(S)

#奇数個ある文字が複数存在していないかチェック
flag = False
for v in list(count.values()):
    if v%2 == 1:
        if flag:
            print((-1))
            return
        else:
            flag = True

# 各文字が属すべきインデックスを求める
# memo[i] -> S[i]の回文変換後のインデックス(0-indexed)
memo = [None]*(N)
#appearCnt[k] -> 文字kの出現回数
appearCnt = {k:0 for k in list(count.keys())}

# まず、回文時に左半分に属する文字に関して、インデックスを割り当てる。
tInd = 0
for i in range(N):
    s = S[i]
    if appearCnt[s] <= count[s]//2 - 1:
        appearCnt[s] += 1
        memo[i] = tInd
        tInd += 1

#奇数個ある文字がある場合は、真ん中になる文字に関して、インデックスを割り当てる
if flag:
    for i in range(N):
        s = S[i]
        if count[s]%2 == 1 and memo[i]==None:
            memo[i] = tInd
            break

#回文時に右半分になる文字にインデックスを割り当てる。
#まず、各文字の文字列Sにおける出現回数をまとめる
appearIdx = {k:[] for k in list(count.keys())}
for i in range(N):
    s = S[i]
    appearIdx[s].append(i)

for v in list(appearIdx.values()):
    for i in range(len(v)//2):
        l = v[i]
        r = v[len(v)-i-1]
        memo[r] = (N-1)-memo[l]
ans = 0
bit = BIT(N)
for i in range(N):
    bit.add(memo[i]+1,1)
    ans += bit.sum(N)-bit.sum(memo[i]+1)
print(ans)



class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0]*(n+1)

    def __iter__(self):
        psum = 0
        for i in range(self.size):
            csum = self.sum(i+1)
            yield csum - psum
            psum = csum
        raise StopIteration()

    def __str__(self):  # O(nlogn)
        return str(list(self))

    def sum(self, i):
        # [0, i) の要素の総和を返す
        if not (0 <= i <= self.size): raise ValueError("error!")
        s = 0
        while i>0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        if not (0 <= i < self.size): raise ValueError("error!")
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def __getitem__(self, key):
        if not (0 <= key < self.size): raise IndexError("error!")
        return self.sum(key+1) - self.sum(key)

    def __setitem__(self, key, value):
        # 足し算と引き算にはaddを使うべき
        if not (0 <= key < self.size): raise IndexError("error!")
        self.add(key, value - self[key])



S = input()
N = len(S)
cnt = [0]*26
for c in S:
    cnt[ord(c)-97] += 1
odd = -1
for i, cn in enumerate(cnt):
    if cn%2 != 0:
        if odd == -1:
            odd = i
        else:
            print((-1))
            return
    cnt[i] //= 2
#cnt2 = [0]*26
L = [[] for _ in range(26)]
n = N//2 + 1
B = []
for c in S:
    c_int = ord(c)-97
    if cnt[c_int] == 0:
        if c_int == odd:
            B.append(1)
            odd = -1
        else:
            p = L[c_int].pop()
            B.append(p)
    else:
        L[c_int].append(n)
        B.append(0)
        n-=1
        cnt[c_int] -= 1

bit = Bit(N//2+2)
ans = 0
for i, b in enumerate(B):
    ans += i - bit.sum(b+1)
    bit.add(b, 1)
print(ans)


from collections import Counter
import sys
s = input()
N = len(s)
sc = Counter(s)
odds = [1 for x in sc if sc[x] % 2 == 1]
if len(odds) > 1:
    print((-1))
    return

class BIT:
    def __init__(self, size):
        self.bit = [0] * (size+1)
    def add(self, index, elem):
        index += 1
        while index < len(self.bit):
            self.bit[index] += elem
            index += index & -index
    def get(self, index):
        index += 1
        ret = 0
        while 0 < index:
            ret += self.bit[index]
            index -= index & -index
        return ret

indices = [-1] * N
tb = {c: [None] * (sc[c]//2) for c in sc}
lens = {c: 0 for c in sc}
p = 0
for i in range(N):
    c = s[i]
    l = lens[c]
    if 2 * (l+1) <= sc[c]:
        indices[p] = i
        tb[c][l] = p
        lens[c] += 1
        p += 1
    elif 2 * (l+1) == sc[c] + 1:
        indices[N//2] = i
        lens[c] += 1
    else:
        indices[N-1-tb[c][sc[c]-l-1]] = i
        lens[c] += 1

ans = 0
bit = BIT(N)
for i in indices:
    bit.add(i, 1)
    ans += bit.get(N-1) - bit.get(i)
print(ans)


a2n=lambda x:ord(x)-ord('a')
# 数値(1〜26)→アルファベット(a〜z)
n2a = lambda x:chr(x+ord('a')).lower()

s=list(map(a2n,list(input())))
n=len(s)
cary=[0]*26
from collections import deque
ary=[deque([]) for _ in range(26)]
for i,x in enumerate(s):
  cary[x]+=1
  ary[x].append(i)
oddcnt=0
for x in cary:
  if x%2==1:oddcnt+=1
if oddcnt>1:
  print(-1)
  return

# 0-indexed binary indexed tree
class BIT:
  def __init__(self, n):
    self.n = n
    self.data = [0]*(n+1)
    self.el = [0]*(n+1)
  # sum of [0,i) sum(a[:i])
  def sum(self, i):
    if i==0:return 0
    s = 0
    while i > 0:
      s += self.data[i]
      i -= i & -i
    return s
  def add(self, i, x):
    i+=1
    self.el[i] += x
    while i <= self.n:
      self.data[i] += x
      i += i & -i
  # sum of [l,r)   sum(a[l:r])
  def sumlr(self, i, j):
    return self.sum(j) - self.sum(i)
  # a[i]
  def get(self,i):
    i+=1
    return self.el[i]

bit=BIT(n)
for i in range(n):
  bit.add(i,1)
ans=0
m=n
for i in range(n//2):
  # idx=i,n-1-iにくるものを考える
  t=-1
  v=float('inf')
  for j in range(26):
    if not ary[j]:continue
    l=ary[j][0]
    r=ary[j][-1]
    tmp=0
    # lからiへ
    tmp+=bit.sum(l)
    # rからn-1-iへ
    tmp+=m-2*i-bit.sum(r+1)
    if v>tmp:
      v=tmp
      t=j
  r=ary[t].pop()
  l=ary[t].popleft()
  bit.add(l,-1)
  bit.add(r,-1)
  ans+=v
print(ans)

from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from itertools import permutations, accumulate, combinations, combinations_with_replacement
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce, lru_cache  # @lru_cache(None)
from fractions import gcd
import sys
def input(): return sys.stdin.readline().rstrip()
def I(): return int(input())
def Is(): return (int(x) for x in input().split())
def LI(): return list(Is())
def TI(): return tuple(Is())
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()
def LS(): return list(S())
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(10**6)
MOD = 10**9+7
INF = 10**18
# ----------------------------------------------------------- #

class BinaryIndexedTree:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):  # 1-index
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):  # 1-index
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    """
    # 使用例
    bit = BinaryIndexedTree(10)     # 要素数を与えてインスタンス化
    bit.add(2, 10)    # a2に10を加える
    bit.add(3, -6)    # a3に-6を加える
    print(bit.sum(6)) # a1～a6の合計を返す
    print(bit.sum(6) - bit.sum(3))  # a4～a6の合計を返す
    """

s = S()
n = len(s)
s_index = defaultdict(list)
for i, x in enumerate(s):
    s_index[x].append(i)

T = [0]*n  # sでi番目の文字は、最終的な回文でT[i]番目の文字となる
flag = False  # 奇数個の文字が前にあったかフラグ(奇数個の文字が2つ以上あってはならない)
AC = []  # 最終的な回文での前半Aと後半Cのペア
for x, index_list in s_index.items():
    count = len(index_list)
    if count % 2 == 1:
        if flag:
            print(-1)
            return
        else:
            flag = True
            mid = index_list[count//2]
            T[mid] = n//2  # 回文の中心(B)
    for i in range(count//2):
        a = index_list[i]
        c = index_list[-i-1]
        AC.append((a, c))

AC.sort(key=itemgetter(0))  # 前半(a)の順番でソート
for i, (a, c) in enumerate(AC):
    T[a] = i  # a == i
    T[c] = n - i - 1

BIT = BinaryIndexedTree(n)
inversion = 0
for i, t in enumerate(T):
    i += 1  # 1-indexに変換
    t += 1  # 1-indexに変換
    BIT.add(t, 1)
    inversion += i - BIT.sum(t)
print(inversion)

# Binary Indexed Tree (Fenwick Tree)
class BIT():
    """一点加算、区間取得クエリをそれぞれO(logN)で答える
    add: i番目にvalを加える
    get_sum: 区間[l, r)の和を求める
    i, l, rは0-indexed
    """
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def _sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def add(self, i, val):
        """i番目にvalを加える"""
        i = i + 1
        while i <= self.n:
            self.bit[i] += val
            i += i & -i

    def get_sum(self, l, r):
        """区間[l, r)の和を求める"""
        return self._sum(r) - self._sum(l)


import copy

s = input()
n = len(s)
memo = {}
for i in range(n):
    if s[i] not in memo:
        memo[s[i]] = 1
    else:
        memo[s[i]] += 1

odd_cnt = 0
for i in memo:
    odd_cnt += memo[i] % 2
if odd_cnt > 1:
    print(-1)
    return

left = []
right = []

memo2 = copy.deepcopy(memo)
ans_cnt = 0
word = ""
for i in range(n):
    if memo2[s[i]]*2 > memo[s[i]] + 1:
        memo2[s[i]] -= 1
        ans_cnt += i - len(left)
        left.append(s[i])
    elif memo2[s[i]]*2 == memo[s[i]] + 1:
        word = s[i]
        memo2[s[i]] -= 1
        right.append(s[i])
    else:
        memo2[s[i]] -= 1
        right.append(s[i])
 
if word != "":
    for i in range(len(right)):
        if right[i] == word:
            ans_cnt += i
            del(right[i])
            break
right = right[::-1]

memo = {}
for i in range(len(right)):
    if right[i] not in memo:
        memo[right[i]] = [i]
    else:
        memo[right[i]].append(i)
for i in memo:
    memo[i] = memo[i][::-1]

for i in range(len(left)):
    tmp = left[i]
    left[i] = memo[tmp][-1]
    del(memo[tmp][-1])

memo = {}
for i in range(len(left)):
    memo[i] = left[i]

bit = BIT(len(left))
for i in range(len(left)):
    bit.add(memo[i], 1)
    ans_cnt += bit.get_sum(memo[i] + 1, len(left))
print(ans_cnt)

from collections import defaultdict
S = input()

class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def update(self, i, v):
        while i <= self.n:
            self.bit[i] += v
            i += i & -i
            
    def query(self, i):
        ret = 0
        while i > 0:
            ret += self.bit[i]
            i -= i & -i
            
        return ret

d = defaultdict(list)
for i, v in enumerate(S):
    d[v].append(i + 1)

if sum(len(l) % 2 != 0 for l in list(d.values())) > 1:
    print((-1))
    return

N = len(S)
ctr = []
key_map = [-1] * (N + 1)

for k, v in list(d.items()):
    t = len(v)
    if t % 2  == 1:
        key_map[v[t // 2]] = N // 2 + 1

    for j in range(t // 2):
        ctr.append((v[j], v[-j - 1]))
        
ctr.sort()

for i, (l, r) in enumerate(ctr):
    key_map[l] = i + 1
    key_map[r] = N - i

tree = BIT(N)
ans = 0
for i, v in enumerate(key_map[1:]):
    ans += i - tree.query(v)
    tree.update(v, 1)
print(ans)


import sys
input = sys.stdin.readline

S = list(input().rstrip())
L = len(S)

# binary indexed tree
bit = [0 for _ in range(L+1)]

# 0からiまでの区間和
# 立っているビットを下から処理
def query_sum(i):
    s = 0
    while i > 0:
        s += bit[i]
        i -= i & -i
    return s

# i番目の要素にxを足す
# 覆ってる区間すべてに足す
def add(i, x):
    while i <= L:
        bit[i] += x
        i += i & -i

def main():
    A = {}
    for i, s in enumerate(S):
        if not s in A.keys():
            A[s] = [i]
        else:
            A[s].append(i)
    odd = 0
    dic = {}
    for al, c in A.items():
        dic[al] = 0
        if len(c)%2 != 0:
            odd += 1
    if odd > 1:
        print(-1)
    else:
        make_ind = []
        for s, B in A.items():
            l = len(B)
            if l%2 == 1:
                mid = B[l//2]
            for j, b in enumerate(B):
                if j < l//2:
                    make_ind.append(b)
        make_ind.sort()
        IND = [None]*L
        for i, m in enumerate(make_ind):
            s = S[m]
            IND[m] = i+1
            inv = A[s][len(A[s])-1-dic[s]]
            IND[inv] = L-i
            dic[s] += 1
        if L%2 == 1:
            IND[mid] = L//2+1
        

        ans = 0
        for j, a in enumerate(IND):
            ans += j - query_sum(a)
            add(a, 1)
        
        print(ans)

def __starting_point():
    main()
__starting_point()

from collections import deque
alphabetlist=['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']

S=input()
N=len(S)

dic={moji:deque([]) for moji in alphabetlist}
for i in range(N):
    dic[S[i]].append(i+1)

left=deque([])
right=deque([])
mid=[]

if N%2==1:
    check=0
    memo=0
    for moji in dic:
        if len(dic[moji])%2==1:
            k=len(dic[moji])
            check+=1
            memo=dic[moji][k//2]
    if check!=1:
        print(-1)
        return
    else:
        mid.append(memo)
else:
    check=0
    for moji in dic:
        if len(dic[moji])%2==1:
            print(-1)
            return

for i in range(N//2):
    for moji in alphabetlist:
        if len(dic[moji])>=2:
            L=dic[moji][0]
            R=dic[moji][-1]
            for moji2 in alphabetlist:
                if len(dic[moji2])>=2 and dic[moji2][0]<L<R<dic[moji2][-1]:
                    break
            else:
                left.append(L)
                right.appendleft(R)
                dic[moji].popleft()
                dic[moji].pop()
                break

ans=list(left)+mid+list(right)
n=N
#A1 ... AnのBIT(1-indexed)
BIT = [0]*(n+1)

#A1 ~ Aiまでの和 O(logN)
def BIT_query(idx):
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum

#Ai += x O(logN)
def BIT_update(idx,x):
    while idx <= n:
        BIT[idx] += x
        idx += idx&(-idx)
    return

res=0
for i in range(N):
    res+=i-BIT_query(ans[i])
    BIT_update(ans[i],1)

print(res)

"""
どれとペアになるかは最初から確定
位置を決めれば後は転倒数
"""
import sys

def bitadd(a,w,bit): #aにwを加える(1-origin)
 
    x = a
    while x <= (len(bit)-1):
        bit[x] += w
        x += x & (-1 * x)
 
def bitsum(a,bit): #ind 1～aまでの和を求める
 
    ret = 0
    x = a
    while x > 0:
        ret += bit[x]
        x -= x & (-1 * x)
    return ret


S = input()

dic = {}

for i,s in enumerate(S):

    if s not in dic:

        dic[s] = []

    dic[s].append(i)

pair = [None] * len(S)
lis = [None] * len(S)

for i in dic:

    for j in range(len(dic[i]) // 2):

        pair[dic[i][j]] = dic[i][-1-j]
        pair[dic[i][-1-j]] = -1

numnone = 0
for i in pair:
    if i == None:
        numnone += 1

if numnone > 1:
    print((-1))
    return

nmax = 0
for i,num in enumerate(pair):

    if num == None:
        lis[i] = len(S)//2

    if num != None and num >= 0:
        
        lis[i] = nmax
        lis[num] = len(S)-1-nmax
        nmax += 1

BIT = [0] * (len(S)+1)
ans = 0
lis.reverse()

for i,num in enumerate(lis):

    num += 1
    ans += bitsum(num,BIT)
    bitadd(num,1,BIT)

print (ans)


from string import ascii_lowercase


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


def solve(s):
    indices = {c: [] for c in ascii_lowercase}
    for i, c in enumerate(s):
        indices[c].append(i)

    n = len(s)
    center = n // 2
    bubbles = [-1] * n
    odd_flag = False
    lefts, rights = [], []
    used = [False] * n
    for c, ids in list(indices.items()):
        cnt = len(ids)
        if cnt & 1:
            if odd_flag:
                return -1
            odd_flag = True
            bubbles[ids[cnt // 2]] = center + 1
            used[center] = True
        for i in range(cnt // 2):
            li, ri = ids[i], ids[-i - 1]
            if li < center:
                lefts.append((li, ri))
                used[n - li - 1] = True
            else:
                rights.append((li, ri))
    lefts.sort()
    rights.sort()
    r_itr = iter(rights)
    # print(lefts)
    # print(rights)
    for i, (li, ri) in enumerate(lefts):
        bubbles[li] = i + 1
        bubbles[ri] = n - i
    for i in range(len(lefts), center):
        li, ri = next(r_itr)
        bubbles[li] = i + 1
        bubbles[ri] = n - i
    # print(bubbles)

    ans = 0
    bit = Bit(n)
    for i, m in enumerate(bubbles):
        ans += i - bit.sum(m)
        bit.add(m, 1)
    return ans


print((solve(input())))


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 calc_inv(arr):
    N = len(set(arr))
    atoi = {a: i for i, a in enumerate(sorted(set(arr)))}
    bit = fenwick_tree(N)
    res = 0
    for i, a in enumerate(arr):
        res += i - bit.sum(0, atoi[a] + 1)
        bit.add(atoi[a], 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
        half = {k: v // 2 for k, v in C.items()}
        cnt = {k: 0 for k in C.keys()}
        label = []
        left = []
        right = []
        for i, s in enumerate(S):
            if cnt[s] < half[s]:
                label.append(0)
                left.append(s)
            else:
                label.append(1)
                right.append(s)
            cnt[s] += 1
        ans = calc_inv(label)

        pos = {k: [] for k in C.keys()}
        for i, s in enumerate(left):
            pos[s].append(i)
        label = []
        for s in right:
            label.append(pos[s].pop())
        ans += calc_inv(label[::-1])
        return ans

    else:  # 奇数
        if odd != 1:
            return -1
        half = {k: v // 2 for k, v in C.items()}
        cnt = {k: 0 for k in C.keys()}
        label = []
        right = []
        left = []
        seen = 0
        LL = 0  # midの右にあるL
        RR = 0  # midの左にあるR

        for i, s in enumerate(S):
            if s == mid and cnt[s] == half[s]:
                seen = 1
                cnt[s] += 1
                continue
            if cnt[s] < half[s]:
                label.append(0)
                left.append(s)
                if seen:
                    LL += 1
            else:
                label.append(1)
                right.append(s)
                if not seen:
                    RR += 1
            cnt[s] += 1
        ans = calc_inv(label)
        ans += RR + LL

        pos = {k: [] for k in C.keys()}
        for i, s in enumerate(left):
            pos[s].append(i)
        label = []
        for s in right:
            label.append(pos[s].pop())
        ans += calc_inv(label[::-1])
        return ans


print(main())

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)
    return

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))

class segment_tree_dual:
    def __init__(self, N, compose, funcval, ID_M=None):
        self.compose = compose
        self.ID_M = ID_M
        self.funcval = funcval

        self.height = (N-1).bit_length() #木の段数
        self.N0 = 1<<self.height #木の横幅 >= N
        self.laz = [self.ID_M]*(2*self.N0) #作用素の木
        self.val = None #値の配列

    #初期値の配列を作る
    def build(self,initial):
        self.val = initial[:]

    #laz[k] を子に伝える、k が一番下の場合は laz[k] を val に反映する
    def propagate(self,k):
        if self.laz[k] == self.ID_M: return;
        if self.N0 <= k:
            self.val[k-self.N0] = self.funcval(self.val[k-self.N0], self.laz[k])
            self.laz[k] = self.ID_M
        else:
            self.laz[(k<<1)  ] = self.compose(self.laz[(k<<1)  ],self.laz[k]);
            self.laz[(k<<1)+1] = self.compose(self.laz[(k<<1)+1],self.laz[k]);
            self.laz[k] = self.ID_M;
    
    # 遅延をすべて解消する
    def propagate_all(self):
        upto = self.N0 + len(self.val)
        for i in range(1,upto): self.propagate(i)

    # laz[k]およびその上に位置する作用素をすべて伝播
    def thrust(self,k):
        for i in range(self.height,-1,-1): self.propagate(k>>i)

    # 区間[l,r]に関数 f を作用
    def update(self, L,R,f):
        L += self.N0; R += self.N0+1
        """まず伝播させる（オペレータが可換なら必要ない）"""
        #self.thrust(L)
        #self.thrust(R-1)
        #登りながら関数 f を合成
        while L < R:
            if R & 1:
                R -= 1
                self.laz[R] = self.compose(self.laz[R],f)
            if L & 1:
                self.laz[L] = self.compose(self.laz[L],f)
                L += 1
            L >>= 1; R >>= 1
    
    # values[k] を取得。
    def point_get(self, k):
        res = self.val[k]
        k += self.N0
        while k:
            if self.laz[k] != self.ID_M:
                res = self.funcval(res, self.laz[k])
            k //= 2
        return res
    
    # values[k] = x 代入する
    def point_set(self, k): 
        self.thrust(k+self.N0)
        self.val[k] = x



# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

#x,y = map(int,readline().split())
from collections import deque
s = input()
lst = [deque() for _ in range(26)]
for i,c in enumerate(s):
    lst[ord(c)-97].append(i)

c = 0
for l in lst:
    if len(l)%2==1: c += 1
if c >= 2:
    print((-1))
    return

n = len(s)
L = 0
R = n-1
from operator import add
seg = segment_tree_dual(n, compose=add, funcval=add, ID_M=0)
seg.build([0]*n)

ans = 0
INF = 1<<30
for i in range(n//2):
    I = -1
    v = INF
    for idx in range(26):
        if lst[idx]:
            a,b = lst[idx][0], lst[idx][-1]
            d = a+seg.point_get(a)-i + n-1-i-(b+seg.point_get(b))
            #print(i,d,lst[idx],a+seg.point_get(a),(b+seg.point_get(b)))
            if d < v:
                I = idx
                v = d
    #print(v,I,lst[I],a,seg.point_get(a),n-1,(b+seg.point_get(b)))
    seg.update(0,lst[I].popleft(),1)
    seg.update(lst[I].pop(),n-1,-1)
    ans += v

print(ans)






import sys
class BIT():
    def __init__(self,number):
        self.n=number
        self.list=[0]*(number+1)
        
    def add(self,i,x):#ith added x  1indexed
        while i<=self.n:
            self.list[i]+=x
            i+=i&-i
            
    def search(self,i):#1-i sum
        s=0
        while i>0:
            s+=self.list[i]
            i-=i&-i
        return s
    
    def suma(self,i,j):#i,i+1,..j sum
        return self.search(j)-self.search(i-1)
#from collections import defaultdict
S=input()
N = len(S)
L = 26
a = ord('a')
d = [[] for i in range(L)]
for i in range(N):
    s=ord(S[i])-a
    d[s].append(i)
flag=0
for i in range(L):
    if len(d[i])%2==1:
        flag+=1
if flag>1:
    print(-1)
    return
Suc=[-1]*N
pairs=[]
for i in range(L):
    T=len(d[i])
    for s in range((T//2)):
        li,ri=d[i][s],d[i][-s-1]
        pairs.append((li,ri))
    if T%2==1:
        Suc[d[i][T//2]]=(N//2)+1
pairs.sort()
for i, (li,ri) in enumerate(pairs):
    Suc[li]=i+1
    Suc[ri]=N-i
Tree=BIT(N+3)
ans=0
for i,m in enumerate(Suc):
    ans+=i-Tree.search(m)
    Tree.add(m,1)
#ans+=Tree.search(N+1)
print(ans)

s = input()
cnt = [0] * 26
n = len(s)

for c in s:
    cnt[ord(c) - ord('a')] += 1

odd = -1
for i in range(26):
    if cnt[i] % 2 == 1:
        if odd != -1:
            print(-1)
            return
        odd = i

cnt2 = [[] for i in range(26)]
nums = []
left = 0
for i in range(len(s)):
    c = s[i]
    ind = ord(c) - ord('a')
    if len(cnt2[ind]) * 2 + 1 == cnt[ind]:
        cnt2[ind].append((n-1)//2)
        nums.append((n-1)//2)
    elif len(cnt2[ind]) <= (cnt[ind]-1)//2:
        cnt2[ind].append(left)
        nums.append(left)
        left += 1
    else:
        num = n - 1 - cnt2[ind][cnt[ind]-1-len(cnt2[ind])]
        cnt2[ind].append(num)
        nums.append(num)

ans = 0
#print(nums)
bit = [0] * (n+1)
def add(x):
    nonlocal bit
    x += 1
    while x <= n:
        bit[x] += 1
        x += x & -x

def sum(x):
    x += 1
    res = 0
    while x:
        res += bit[x]
        x -= x & -x
    return res
for num in nums[::-1]:
    ans += sum(num)
    add(num)

print(ans)

#!/usr/bin/env python3

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * n

    def sum(self, i):
        s = 0
        i -= 1
        while i >= 0:
            s += self.tree[i]
            i = (i & (i + 1)) - 1
        return s

    def add(self, i, x):
        while i < self.size:
            self.tree[i] += x
            i |= i + 1

a = ord('a')

def make_index(s):

    index = [[] for _ in range(26)]
    for i, ch in enumerate(s):
        index[ord(ch) - a].append(i)

    return index

def solve(s):

    n = len(s)
    index = make_index(s)

    odd = None
    for code, char_pos in enumerate(index):
        if len(char_pos) % 2 == 1:
            if odd is not None:
                return -1
            odd = code

    bit = Bit(n)

    ans = 0
    cnt = 0
    for i in range(n):
        if bit.sum(i + 1) - bit.sum(i) == 1:
            continue
        code = ord(s[i]) - a
        if code == odd and index[code][-1] == i:
            continue
        cnt += 1
        j = index[code].pop()
        ans += n - cnt - (j - bit.sum(j))
        bit.add(j, 1)
        if n // 2 <= cnt:
            break

    if odd is not None:
        j = index[odd][-1]
        ans += abs(n // 2 - (j - bit.sum(j)))

    return ans


def main():
    s = input()

    print((solve(s)))


def __starting_point():
    main()


__starting_point()

from collections import Counter,defaultdict

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)
c = Counter(s)
flg = 0
if n%2 == 0:
  for i in c.values():
    if i%2:
      print(-1)
      return
else:
  for st,i in c.items():
    if i%2 and flg:
      print(-1)
      return
    elif i%2:
      flg = 1
ans = 0
fstr = []
lstr = []
dc = defaultdict(int)
ptr = 0
for i in range(n):
  si = s[i]
  dc[si] += 1
  cnt = dc[si]
  if c[si]%2:
    if cnt*2-1 == c[si]:
      ans += i-ptr
      continue
  if cnt <= c[si]//2:
    ans += i-ptr
    ptr += 1
    fstr.append(si)
  else:
    lstr.append(si)
lstr = lstr[::-1]
n //= 2
perm = [0]*n
fdc = defaultdict(list)
ldc = defaultdict(int)
lcnt = 0
for i in range(n):
  fi = fstr[i]
  fdc[fi].append(i+1)
for i in range(n):
  li = lstr[i]
  perm[i] = fdc[li][ldc[li]]
  ldc[li] += 1
sol = Bit(n+2)
for i in range(n):
  p = perm[i]
  ans += sol.sum(n+1)-sol.sum(p)
  sol.add(p,1)
print(ans)

from collections import deque
import sys
input = sys.stdin.readline

class FenwickTree:
    def __init__(self, size):
        self.data = [0] * (size + 1)
        self.size = size

    # i is exclusive
    def prefix_sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s

    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.data[i] += x
            i += i & -i

    def lower_bound(self, x):
        if x <= 0:
            return 0
        k = 1
        while k * 2 <= self.size:
            k *= 2
        i = 0
        while k > 0:
            if i + k <= self.size and self.data[i + k] < x:
                x -= self.data[i + k]
                i += k
            k //= 2
        return i


class RangeFenwickTree:
    def __init__(self, size):
        self.bit0 = FenwickTree(size)
        self.bit1 = FenwickTree(size)

    # i is exclusive
    def prefix_sum(self, i):
        return self.bit0.prefix_sum(i) * (i - 1) + self.bit1.prefix_sum(i)

    def add(self, l, r, x):
        self.bit0.add(l, x)
        self.bit0.add(r, -x)
        self.bit1.add(l, -x * (l - 1))
        self.bit1.add(r, x * (r - 1))


class FenwickTree2D:
    def __init__(self, H, W):
        self.H = H
        self.W = W
        self.data = [[0] * (H + 1) for _ in range(W + 1)]

    def add(self, a, b, x):
        a += 1
        b += 1
        i = a
        while i <= self.H:
            j = b
            while j <= self.W:
                self.data[i][j] += x
                j += j & -j
            i += i & -i

    def sum(self, a, b):
        a += 1
        b += 1
        ret = 0
        i = a
        while i > 0:
            j = b
            while j > 0:
                ret += self.data[i][j]
                j -= j & -j
            i -= i & -i
        return ret

S = list(map(lambda c: ord(c) - ord('a'), input().rstrip()))
N = len(S)
idx = [deque() for _ in range(26)]
for i, c in enumerate(S):
    idx[c].append(i)
if sum(len(v) % 2 for v in idx) > 1:
    print(-1)
    return
fw = FenwickTree(N + 1)
for i in range(1, N + 1):
    fw.add(i, 1)
ans = 0
for i in range(N // 2):
    min_cost = float('inf')
    char = -1
    for c in range(26):
        if len(idx[c]) <= 1:
            continue
        l = idx[c][0]
        cost = fw.prefix_sum(l + 1) - i
        r = idx[c][-1]
        cost += N - i - 1 - fw.prefix_sum(r + 1)
        if cost < min_cost:
            min_cost = cost
            char = c
    ans += min_cost
    fw.add(0, 1)
    fw.add(idx[char].popleft(), -1)
    fw.add(idx[char].pop(), -1)
print(ans)

import sys
input = sys.stdin.readline
from collections import deque, defaultdict, Counter

S = input().rstrip()
L = len(S)

c = Counter(S)
if sum((x&1 for x in c.values())) >= 2:
    print(-1)
    return

alphabet_to_pos = defaultdict(deque)

for i,x in enumerate(S,1):
    alphabet_to_pos[x].append(i)

after = [None] * len(S)
n = 0
for i,x in enumerate(S,1):
    p = alphabet_to_pos[x]
    if not p:
        continue
    if len(p) == 1:
        p.pop()
        after[L//2] = i
        continue
    p.popleft()
    j = p.pop()
    after[n] = i
    after[L - n - 1] = j
    n += 1

def BIT_update(tree,x):
    while x <= L:
        tree[x] += 1
        x += x & (-x)

def BIT_sum(tree,x):
    s = 0
    while x:
        s += tree[x]
        x -= x & (-x)
    return s

answer = 0
tree = [0] * (L+1)
for i,x in enumerate(after):
    answer += i - BIT_sum(tree,x)
    BIT_update(tree,x)

print(answer)

from string import ascii_lowercase


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


def solve(s):
    indices = {c: [] for c in ascii_lowercase}
    for i, c in enumerate(s):
        indices[c].append(i)

    n = len(s)
    center = n // 2
    bubbles = [-1] * n
    odd_flag = False
    lefts, rights = [], []
    for c, ids in list(indices.items()):
        cnt = len(ids)
        if cnt & 1:
            if odd_flag:
                return -1
            odd_flag = True
            bubbles[ids[cnt // 2]] = center + 1
        for i in range(cnt // 2):
            li, ri = ids[i], ids[-i - 1]
            if li < center:
                lefts.append((li, ri))
            else:
                rights.append((li, ri))
    lefts.sort()
    rights.sort()
    r_itr = iter(rights)
    for i, (li, ri) in enumerate(lefts):
        bubbles[li] = i + 1
        bubbles[ri] = n - i
    for i in range(len(lefts), center):
        li, ri = next(r_itr)
        bubbles[li] = i + 1
        bubbles[ri] = n - i

    ans = 0
    bit = Bit(n)
    for i, m in enumerate(bubbles):
        ans += i - bit.sum(m)
        bit.add(m, 1)
    return ans


print((solve(input())))


from collections import Counter
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)
    return

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)

import sys
def input():
	return sys.stdin.readline()[:-1]

class BIT():#1-indexed
	def __init__(self, size):
		self.table = [0 for _ in range(size+2)]
		self.size = size

	def Sum(self, i):#1からiまでの和
		s = 0
		while i > 0:
			s += self.table[i]
			i -= (i & -i)
		return s

	def PointAdd(self, i, x):#
		while i <= self.size:
			self.table[i] += x
			i += (i & -i)
		return

s = input()
n = len(s)
a = [-1 for _ in range(n)]
ch = [[] for _ in range(26)]
for i in range(n):
	ch[ord(s[i])-97].append(i)
if sum([len(x)%2 == 1 for x in ch]) > 1:
	print(-1)
	return

for i, c in enumerate(ch):
	tmp = i
	l = len(c)
	for j in range(l//2):
		a[c[j]] = tmp
		a[c[l-j-1]] = tmp
		tmp += 26
#print(a)

former, latter = 0, 0
half = False
d = dict()
cur = 0
bubble = []

ans = 0

for x in a:
	if x >= 0:
		if x not in d:
			d[x] = cur
			cur += 1
			former += 1
			ans += latter + half
		else:
			bubble.append(d[x])
			latter += 1
			if n%2 == 1 and not half:
				ans += 1
	else:
		half = True

bit = BIT(n//2+2)
for b in bubble:
	ans += bit.Sum(b+1)
	bit.PointAdd(b+1, 1)

print(ans)


import sys
from collections import deque, defaultdict
import copy
import bisect
sys.setrecursionlimit(10 ** 9)
import math
import heapq
from itertools import product, permutations,combinations
import fractions

import sys
def input():
	return sys.stdin.readline().strip()

S = input()

alpha = defaultdict(int)
N = len(S)
for i in range(N):
	alpha[S[i]] += 1

num = 0
for n in alpha:
	if alpha[n] % 2 == 1:
		num += 1

if num >= 2:
	print((-1))
	return

alpha_num = defaultdict(deque)
for i in range(N):
	alpha_num[S[i]].append(i)

loc_list = [-1]*N
num = 0
for i in range(N):
	if len(alpha_num[S[i]]) >= 2:
		x = alpha_num[S[i]].popleft()
		y = alpha_num[S[i]].pop()
		loc_list[x] = num
		loc_list[y] = N - 1 - num
		num += 1
	elif len(alpha_num[S[i]]) == 1:
		x = alpha_num[S[i]].popleft()
		loc_list[x] = N // 2

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


bit = Bit(N)
ans = 0



for i, p in enumerate(loc_list):
	bit.add(p + 1, 1)
	ans += i + 1 - bit.sum(p + 1)

print(ans)


from collections import Counter, defaultdict


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)
C = Counter(S)
if len(S) % 2 == 0:
    for x in list(C.values()):
        if x % 2 == 1:
            print((-1))
            return
else:
    cnt = 0
    for x in list(C.values()):
        if x % 2 == 1:
            cnt += 1
        if cnt > 1:
            print((-1))
            return

cnt1 = 1
cnt2 = (N + 1) // 2 + 1
cnt_char = defaultdict(int)
seq = [0] * N
S1 = []
S2 = []
for i, s in enumerate(S):
    cnt_char[s] += 1
    if C[s] % 2 == 1:
        if cnt_char[s] == C[s] // 2 + 1:
            seq[i] = N // 2 + 1
            continue
    if cnt_char[s] <= C[s] // 2:
        seq[i] = cnt1
        cnt1 += 1
        S1.append(s)
    else:
        seq[i] = cnt2
        cnt2 += 1
        S2.append(s)
S2.reverse()

ans = 0
seq.reverse()
bit1 = Bit(N+1)
for i in range(N):
    ans += bit1.sum(seq[i])
    bit1.add(seq[i], 1)

char2idx = defaultdict(list)
for i, s1 in enumerate(S1):
    char2idx[s1].append(i+1)
for x in list(char2idx.keys()):
    char2idx[x].reverse()

seq_ = []
for i, s2 in enumerate(S2):
    seq_.append(char2idx[s2].pop())

bit2 = Bit(N+1)
seq_.reverse()
for i in range(len(seq_)):
    ans += bit2.sum(seq_[i])
    bit2.add(seq_[i], 1)

print(ans)


from collections import defaultdict

class BIT():
    def __init__(self,n):
        self.size=n
        self.bit=[0]*(n+1)
    def add(self,i,x):
        while i<=self.size:
            self.bit[i]+=x
            i+=i&-i
    def sum(self,i):
        s=0
        while i>0:
            s+=self.bit[i]
            i-=i&-i
        return s

s=input()
n=len(s)
idx=defaultdict(list)
for i,c in enumerate(s):
    idx[c].append(i)
ctr=n//2
B=[0]*n
flag=False
P=[]
for c,I in idx.items():
    cnt=len(I)
    if cnt%2:
        if flag:
            print(-1)
            return
        flag=True
        B[I[cnt//2]]=ctr+1
    for i in range(cnt//2):
        l,r=I[i],I[-i-1]
        P.append((l,r))
P.sort()
for i,(l,r) in enumerate(P):
    B[l],B[r]=i+1,n-i
ans=0
bit=BIT(n)
for i,b in enumerate(B):
    ans+=i-bit.sum(b)
    bit.add(b,1)
print(ans)

class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def _sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def add(self, i, val):
        """i番目にvalを加える"""
        i = i + 1
        while i <= self.n:
            self.bit[i] += val
            i += i & -i

    def get_sum(self, l, r):
        """区間[l, r)の和を求める"""
        return self._sum(r) - self._sum(l)
 

def swap_time(array0, array1):
    n = len(array0)
    memo = {}
    for i in range(n)[::-1]:
        if array0[i] not in memo:
            memo[array0[i]] = []
        memo[array0[i]].append(i)
    res = []
    for val in array1:
        ind = memo[val].pop()
        res.append(ind)
    
    bit = BIT(n)
    ans = 0
    for i in range(n):
        bit.add(res[i], 1)
        ans += bit.get_sum(res[i] + 1, n)
    return ans
  
  

ALPH = "abcdefghijklmnopqrstuvwxyz"
s = input()

cnt_memo = {}
for char in s:
    if char not in cnt_memo:
        cnt_memo[char] = 1
    else:
        cnt_memo[char] += 1

odd = ""
for char in cnt_memo:
    if cnt_memo[char] % 2 == 1:
        if odd:
            print(-1)
            return
        else:
            odd = char
            cnt_memo[char] -= 1
            cnt_memo[char] //= 2
    else:
        cnt_memo[char] //= 2

left = []
mid = []
if odd:
    mid = [odd]
right = []
for char in s:
    if odd == char and cnt_memo[char] == 0:
        odd = ""
    elif cnt_memo[char] != 0:
        left.append(char)
        cnt_memo[char] -= 1
    else:
        right.append(char)

ans = 0
ans += swap_time(left + mid + right, list(s))
ans += swap_time(left, right[::-1])
print(ans)

from string import ascii_lowercase


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


def solve(s):
    indices = {c: [] for c in ascii_lowercase}
    for i, c in enumerate(s):
        indices[c].append(i)

    n = len(s)
    center = n // 2
    bubbles = [-1] * n
    odd_flag = False
    pairs = []
    for c, ids in list(indices.items()):
        cnt = len(ids)
        if cnt & 1:
            if odd_flag:
                return -1
            odd_flag = True
            bubbles[ids[cnt // 2]] = center + 1
        for i in range(cnt // 2):
            li, ri = ids[i], ids[-i - 1]
            pairs.append((li, ri))
    pairs.sort()
    for i, (li, ri) in enumerate(pairs):
        bubbles[li] = i + 1
        bubbles[ri] = n - i

    ans = 0
    bit = Bit(n)
    for i, m in enumerate(bubbles):
        ans += i - bit.sum(m)
        bit.add(m, 1)
    return ans


print((solve(input())))


from collections import defaultdict, deque
from heapq import heappop, heappush
from string import ascii_lowercase as abc

class BIT:
    def __init__(self, N):
        # Nは入れたい要素の個数
        self.size = 2 ** (int.bit_length(N+1))
        self.tree = [0]*(self.size + 1)
 
    def sum(self, i):
        res = 0
        while i:
            res += self.tree[i]
            i -= (i & -(i))
        return res
 
    def add(self, i, x):
        if i == 0:
            return
        while i <= self.size:
            self.tree[i] += x
            i += (i & -(i))


D = [deque() for _ in range(26)]
S = input()
N = len(S)

for i in range(len(S)):
    D[ord(S[i])-97].append(i)

M = [len(D[i])%2 for i in range(26)]
if sum(M) >= 2:
    print(-1)
    return

odd = sum(M)

Q = []
for c in range(26):
    if len(D[c]) >= 2:
        l = D[c].popleft()
        r = D[c].pop()
        a = l * 1
        b = N - 1 - r
        if b < a:
            a, b = b, a
        heappush(Q, (a, b, l, r, c))

T = [0]*(N//2)
for i in range(N//2):
    _, _, l, r, c = heappop(Q)
    T[i] = c

    if len(D[c]) >= 2:
        l = D[c].popleft()
        r = D[c].pop()
        a = l * 1
        b = N - 1 - r
        if b < a:
            a, b = b, a
        heappush(Q, (a, b, l, r, c))

L = [[] for i in range(26)]

for i in range(N//2):
    L[T[i]].append(N-1-i)

if odd:
    L[M.index(1)].append(N//2)

for i in range(N//2-1, -1, -1):
    L[T[i]].append(i)

bit = BIT(N)
ans = 0
for i in range(N):
    j = L[ord(S[i]) - 97].pop()
    ans += i - bit.sum(j+1)
    bit.add(j+1, 1)
print(ans)

def f(x):
    return ord(x)-ord("a")

class Bit:
    def __init__(self, n):
        self.n = n
        self.tree = [0]*(n+1)
        self.el = [0]*(n+1)
        self.depth = n.bit_length() - 1

    def sum(self, i):
        """ 区間[0,i) の総和を求める """
        s = 0
        i -= 1
        while i >= 0:
            s += self.tree[i]
            i = (i & (i + 1) )- 1
        return s

    def add(self, i, x):
        self.el[i] += x
        while i < self.n:
            self.tree[i] += x
            i |= i + 1

class BitSet2:
    """ 座標圧縮が必要な場合 """
    def __init__(self, data, A=[]):
        """ BitSetに入り得る値を先読みした物を data に格納 """
        self.data = sorted(list(set(data)))
        self.n = len(self.data)
        self.p = Bit(self.n + 1)
        self.size = 0
        self.flip = 0
        self.code = {}
        self.decode = {}
        for i, b in enumerate(self.data):
            self.code[b] = i
            self.decode[i] = b
        for a in A:
            self.add(a)

    def add(self,x):
        self.p.add(self.code[x], 1)
        self.size += 1
        self.flip += self.size - self.p.sum(self.code[x]+1)

    def remove(self,x):
        self.p.add(x, -1)
        self.size -= 1

    def flip_counter(self):
        return self.flip

####################################################################################################

import sys
input = sys.stdin.readline

S=input().rstrip()
N=len(S)
P=[[] for _ in range(26)]
Q=[]
res=[-1]*N
for i, s in enumerate(S):
    P[f(s)].append(i)
for p in P:
    Np=len(p)
    for i in range(Np//2):
        Q.append((p[Np-1-i]-p[i],p[i],p[Np-1-i]))
    if len(p)%2:
        if res[N//2]!=-1 or N%2==0: print(-1); return
        res[N//2]=p[Np//2]
Q.sort(reverse=True)
for i,q in enumerate(Q):
    d,x,y=q
    res[i]=x
    res[N-1-i]=y

BS = BitSet2(res,res)
print(BS.flip_counter())

from collections import Counter


class BIT():
    """一点加算、区間取得クエリをそれぞれO(logN)で答える
    add: i番目にvalを加える
    get_sum: 区間[l, r)の和を求める
    i, l, rは0-indexed
    """
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def _sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def add(self, i, val):
        """i番目にvalを加える"""
        i = i + 1
        while i <= self.n:
            self.bit[i] += val
            i += i & -i

    def get_sum(self, l, r):
        """区間[l, r)の和を求める"""
        return self._sum(r) - self._sum(l)


def min_swap_times(s, t):
    if Counter(s) != Counter(t):
        return -1

    n = len(s)
    memo = {}
    for i in range(n):
        if s[i] not in memo:
            memo[s[i]] = [i]
        else:
            memo[s[i]].append(i)
    for i in memo:
        memo[i] = memo[i][::-1]

    array = [0] * n
    for i in range(n):
        array[i] = memo[t[i]][-1]
        del(memo[t[i]][-1])    

    memo = {}
    for i in range(n):
        memo[i] = array[i]
    bit = BIT(n)
    res = 0

    for i in range(n):
        bit.add(memo[i], 1)
        res += bit.get_sum(memo[i] + 1, n)
    return res


import copy

s = input()
n = len(s)
memo = {}
for i in range(n):
    if s[i] not in memo:
        memo[s[i]] = 1
    else:
        memo[s[i]] += 1

odd_cnt = 0
for i in memo:
    odd_cnt += memo[i] % 2
if odd_cnt > 1:
    print(-1)
    return

left = []
right = []

memo2 = copy.deepcopy(memo)
ans_cnt = 0
word = ""
for i in range(n):
    if memo2[s[i]]*2 > memo[s[i]] + 1:
        memo2[s[i]] -= 1
        ans_cnt += i - len(left)
        left.append(s[i])
    elif memo2[s[i]]*2 == memo[s[i]] + 1:
        word = s[i]
        memo2[s[i]] -= 1
        right.append(s[i])
    else:
        memo2[s[i]] -= 1
        right.append(s[i])
 
if word != "":
    for i in range(len(right)):
        if right[i] == word:
            ans_cnt += i
            del(right[i])
            break
right = right[::-1]
tmp = min_swap_times(left, right)
if tmp == -1:
    print(-1)
else:
    print(ans_cnt + tmp)

def main():
    from collections import deque

    # 一点更新・一点取得の加法BIT
    class BIT():
        def __init__(self, n):
            self.n = n
            self.maxbit = 2**(len(bin(n))-3)
            self.bit = [0]*(n+1)
            self.allsum = 0

        # 初期化する
        def make_bit(self, a):
            n, bit = self.n, self.bit
            for i, j in enumerate(a):
                x = i+1
                self.allsum += j
                while x < n+1:
                    bit[x] += j
                    x += x & (-x)

        # 位置iに値vを足す
        def add(self, i, v):
            x, n, bit = i+1, self.n, self.bit
            self.allsum += v
            while x < n+1:
                bit[x] += v
                x += x & (-x)

        # 位置0からiまでの和(sum(bit[:i]))を計算する
        def sum(self, i):
            ret, x, bit = 0, i, self.bit
            while x > 0:
                ret += bit[x]
                x -= x & (-x)
            return ret

        # 位置iからjまでの和(sum(bit[i:j]))を計算する
        def sum_range(self, i, j):
            return self.sum(j) - self.sum(i)

        # 和がw以上となる最小のインデックスを求める
        def lowerbound(self, w):
            if w <= 0:
                return 0
            x, k, n, bit = 0, self.maxbit, self.n, self.bit
            while k:
                if x+k <= n and bit[x+k] < w:
                    w -= bit[x+k]
                    x += k
                k //= 2
            return x

    s = input()
    n = len(s)
    alpha, center = 'abcdefghijklmnopqrstuvwxyz', ""
    counter, must, deque_dict = dict(), dict(), dict()
    for c in alpha:
        counter[c] = 0
        deque_dict[c] = deque([])
    for c in s:
        counter[c] += 1
    for i, j in list(counter.items()):
        must[i] = j//2
    if n % 2 == 1:
        for i, j in list(counter.items()):
            if j % 2 == 1:
                if center != "":
                    print((-1))
                    return 0
                else:
                    center = i
    else:
        for i, j in list(counter.items()):
            if j % 2 == 1:
                print((-1))
                return 0
    half = []
    cnt = 0
    for c in s:
        if must[c] > 0:
            must[c] -= 1
            half.append(c)
            cnt += 1
        if cnt == n//2:
            break
    half2 = half[::-1]
    if center != "":
        half.append(center)
    s2 = half+half2

    for i in range(n):
        deque_dict[s[i]].append(i)

    ans = 0
    s3 = []
    for c in s2:
        d = deque_dict[c].popleft()
        s3.append(d)

    bit = BIT(n)

    for i in s3:
        ans += bit.sum_range(i, n)
        bit.add(i, 1)
    print(ans)


main()


*S, = map(ord, input())
N = len(S)
L = 26
ca = ord('a')
d = [[] for i in range(L)]
for i, c in enumerate(S):
    d[c-ca].append(i)

odd = 0
for v in d:
    if len(v) % 2:
        odd += 1
if not odd <= N%2:
    print(-1)
    return

data = [0]*(N+1)
def add(k, x):
    while k <= N:
        data[k] += x
        k += k & -k
def get(k):
    s = 0
    while k:
        s += data[k]
        k -= k & -k
    return s

M = [None]*N
for v in d:
    vl = len(v)
    for i in range(vl):
        if not i <= vl-1-i:
            break
        p = v[i]; q = v[-i-1]
        M[p] = q
        M[q] = p
cnt = 0
B = [0]*N
for i in range(N-1, -1, -1):
    if M[i] <= i:
        B[i] = B[M[i]] = cnt
        cnt += 1

cur = -1
ans = 0
for i in range(N-1, -1, -1):
    if cur < B[i]:
        cur = B[i]
        if M[i] == i:
            ans += N//2 - cur
        else:
            ans += M[i] - get(M[i]+1)
        add(M[i]+1, 1)
print(ans)

def count_inversions(L):
  def helper(A,B):
    lA,lB = len(A),len(B)
    if lA == 0:
      return B,0
    elif lB == 0:
      return A,0
    
    A,c1 = helper(A[:lA//2],A[lA//2:])
    B,c2 = helper(B[:lB//2],B[lB//2:])
    cnt = c1+c2
    i = 0
    j = 0

    C = [None]*(lA+lB)
    while i < lA and j < lB:
      if A[i] > B[j]:
        cnt += lA-i
        C[i+j] = B[j]
        j += 1
      else:
        C[i+j] = A[i]
        i += 1

    if i < lA:
      C[i+j:] = A[i:]
    else:
      C[i+j:] = B[j:]

    return C,cnt

  return helper(L[:len(L)//2],L[len(L)//2:])[1]

from collections import deque

ALPHABETS = 26

indices = [deque() for _ in range(26)]
S = list([ord(c)-ord('a') for c in input()])
for i,c in enumerate(S):
  indices[c] += [i]

odd = None
for c,l in enumerate(indices):
  if len(l)%2 == 1:
    if odd is None:
      odd = c
    else:
      odd = -1
      break

if odd == -1:
  print((-1))
  return

target = [None]*len(S)
assigned = [False]*len(S)
if odd is not None:
  l = list(indices[odd])
  i = l[len(l)//2]
  target[len(target)//2] = i
  assigned[i] = True
  l = deque(l[:len(l)//2] + l[len(l)//2+1:])

j = 0
for i in range(len(S)//2):
  while assigned[j]:
    j += 1

  l = indices[S[j]]
  a = l.popleft()
  b = l.pop()
  assert a == j
  target[i] = a
  target[len(S)-i-1] = b
  assigned[a] = True
  assigned[b] = True
  
print((count_inversions(target)))


from collections import defaultdict

a = list(map(ord, input()))
N = len(a)
La = ord("a")

data = [0]*(N+1)


d = [[] for i in range(26)]
for i , c in enumerate(a):
    d[c-La].append(i)

odd = 0
for v in d:
    if len(v) % 2:
        odd += 1
if not odd <= N%2:
    print((-1))
    return

data = [0]*(N+1)
def add(k, x):
    while k <= N:
        data[k] += x
        k += k & -k
def get(k):
    s = 0
    while k:
        s += data[k]
        k -= k & -k
    return s

M = [None]*N
for v in d:
    vl = len(v)
    for i in range(vl):
        if not i <= vl-1-i:
            break
        p = v[i]; q = v[-i-1]
        M[p] = q
        M[q] = p
cnt = 0
B = [0]*N
for i in range(N-1, -1, -1):
    if M[i] <= i:
        B[i] = B[M[i]] = cnt
        cnt += 1

cur = -1
ans = 0
for i in range(N-1, -1, -1):

    if cur < B[i]:
        cur = B[i]
        if M[i] == i:
            ans += N//2 - cur
        else:
            ans += M[i] - get(M[i]+1)
        add(M[i]+1, 1)
print(ans)