Problem:
 Score : 800 points    Problem 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.      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 1 eel      Sample Output 1 1  We can turn S into a palindrome by the following operation:   Swap the 2 -nd and 3 -rd characters. S is now ele .        Sample Input 2 ataatmma      Sample Output 2 4  We can turn S into a palindrome by the following operation:   Swap the 5 -th and 6 -th characters. S is now ataamtma .  Swap the 4 -th and 5 -th characters. S is now atamatma .  Swap the 3 -rd and 4 -th characters. S is now atmaatma .  Swap the 2 -nd and 3 -rd characters. S is now amtaatma .        Sample Input 3 snuke      Sample Output 3 -1  We cannot turn S into a palindrome.

Solution (Python):
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 C.values():
        if x % 2 == 1:
            print(-1)
            exit()
else:
    cnt = 0
    for x in C.values():
        if x % 2 == 1:
            cnt += 1
        if cnt > 1:
            print(-1)
            exit()

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

Solution (Python):
import sys
input = sys.stdin.readline

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


bit = [0 for _ in range(L+1)]



def query_sum(i):
    s = 0
    while i > 0:
        s += bit[i]
        i -= i & -i
    return s



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)

if __name__ == "__main__":
    main()

Solution (Python):

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

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)

Solution (Python):
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 d.values()) > 1:
    print(-1)
    exit()

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

for k, v in 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)

Solution (Python):
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)
    exit()

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)

Solution (Python):
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)
    exit()

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)

Solution (Python):
from collections import defaultdict, deque
from heapq import heappop, heappush
from string import ascii_lowercase as abc

class BIT:
    def __init__(self, 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)
    exit()

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)

Solution (Python):
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)
    exit(0)

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)

Solution (Python):
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)

Solution (Python):
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):  
        return str(list(self))

    def sum(self, 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):
        
        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)
            exit()
    cnt[i] //= 2

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)

Solution (Python):
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 index.items():
    cnt = len(k)
    if cnt % 2:
        if flag == 1:
            print(-1)
            exit()
        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)

Solution (Python):
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)
            exit()
        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)

Solution (Python):


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


if __name__ == '__main__':
    main()

Solution (Python):
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)
      exit()
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))

Solution (Python):
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)
      exit()
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)

Solution (Python):
import sys
class BIT():
    def __init__(self,number):
        self.n=number
        self.list=[0]*(number+1)
        
    def add(self,i,x):
        while i<=self.n:
            self.list[i]+=x
            i+=i&-i
            
    def search(self,i):
        s=0
        while i>0:
            s+=self.list[i]
            i-=i&-i
        return s
    
    def suma(self,i,j):
        return self.search(j)-self.search(i-1)

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)
    sys.exit()
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)

print(ans)

Solution (Python):


import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq,string






def solve(f):
    s = f.read_str()
    n = len(s)
    d = [collections.deque() for _ in xrange(26)]
    p = [-1] * n

    for i, si in enumerate(s):
        d[ord(si)-ord('a')].append(i+1)

    odd = None
    for i in xrange(26):
        if len(d[i])%2 == 1:
            if odd is not None: return -1
            odd = i

    if odd is not None: p[n/2] = d[odd][len(d[odd])/2]

    for i in xrange(1,n/2+1):
        mi = float('inf')
        si = None
        for j in xrange(26):
            if len(d[j]) < 2: continue
            if d[j][0] < mi:
                mi = d[j][0]
                si = j

        p[i-1] = d[si].popleft()
        p[n-i] = d[si].pop()

    return count_inversion(p)


class BinaryIndexedTree(object):
    """Binary Indexed Tree (1-indexed)"""
    def __init__(self, size, default=0):
        self.bit = [default for _ in xrange(size + 1)]
        self.size = size

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

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


def count_inversion(a):
    n = len(a)
    ans = 0
    bit = BinaryIndexedTree(n)
    for i in xrange(n):
        ans += i - bit.sum(a[i])
        bit.add(a[i], 1)
    return ans


class Reader(object):
    def __init__(self, filename=None):
        self.file = open(filename) if filename is not None else None
        self.case = 1

    def __readline(self):
        return self.file.next().strip() if self.file else raw_input()

    def next_case(self):
        self.file.next()
        self.case += 1

    def read_int(self): return int(self.__readline())
    def read_float(self): return float(self.__readline())
    def read_long(self): return long(self.__readline())
    def read_decimal(self): return decimal.Decimal(self.__readline())
    def read_str(self): return self.__readline()

    def read_int_list(self): return map(int, self.__readline().split())
    def read_float_list(self): return map(float, self.__readline().split())
    def read_long_list(self): return map(long, self.__readline().split())
    def read_decimal_list(self): return map(decimal.Decimal, self.__readline().split())
    def read_str_list(self): return self.__readline().split()

if __name__ == '__main__':
    filename = sys.argv[1] if len(sys.argv) > 1 else None
    f = Reader(filename)
    if f.file:
        while True:
            print "Case 
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print solve(f)

Solution (Python):
*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)
    exit(0)

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)

Solution (Python):
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)
    sys.exit(0)

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)

Solution (Python):
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 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()))

Solution (Python):
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 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()))

Solution (Python):
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 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)
    
    
    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()))

Solution (Python):
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(map(lambda c: ord(c)-ord('a'),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)
  exit()

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