AtCoder Regular Contest 088 - Papple Sort

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: HARD

Starter code:

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


import os
import sys
from collections import Counter

class BinaryIndexedTree:

	def __init__(self, size):
		self._bit = [0] * size
		self._size = size

	def add(self, i, w):
		x = i + 1
		while x <= self._size:
			self._bit[x - 1] += w
			x += x & -x

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

	def __len__(self):
		return self._size
if os.getenv('LOCAL'):
	sys.stdin = open('_in.txt', 'r')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
IINF = 10 ** 18
MOD = 10 ** 9 + 7
S = sys.stdin.buffer.readline().decode().rstrip()
counter = Counter(S)
if len(S) % 2 == 0:
	ok = True
	for (c, cnt) in counter.items():
		ok &= cnt % 2 == 0
else:
	odds = 0
	for (c, cnt) in counter.items():
		odds += cnt % 2 == 1
	ok = odds == 1
if not ok:
	print(-1)
	exit()
counts = [0] * 26
ls = []
mid = []
rs = []
invs = 0
for c in S:
	n = ord(c) - ord('a')
	counts[n] += 1
	if counter[c] & 1:
		if counts[n] <= counter[c] // 2:
			ls.append(c)
			invs += len(rs) + len(mid)
		elif counts[n] == counter[c] // 2 + 1:
			mid.append(c)
			invs += len(rs)
		else:
			rs.append(c)
	elif counts[n] <= counter[c] // 2:
		ls.append(c)
		invs += len(rs) + len(mid)
	else:
		rs.append(c)
rs = rs[::-1]
l_idx = [[] for _ in range(26)]
for (i, c) in enumerate(ls):
	n = ord(c) - ord('a')
	l_idx[n].append(i)
counts = [0] * 26
idx = []
for (i, c) in enumerate(rs):
	n = ord(c) - ord('a')
	idx.append(l_idx[n][counts[n]])
	counts[n] += 1
invs2 = 0
bit = BinaryIndexedTree(size=len(ls))
for i in reversed(idx):
	invs2 += bit.sum(i)
	bit.add(i, 1)
ans = invs + invs2
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)
	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)


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)


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)
			exit()
		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
bit = [0] * (n + 1)

def add(x):
	global 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)


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)


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 = i + 1
		while i <= self.n:
			self.bit[i] += val
			i += i & -i

	def get_sum(self, 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 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)
			exit()
else:
	for (st, i) in c.items():
		if i % 2 and flg:
			print(-1)
			exit()
		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 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)


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):
		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):
		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
		RR = 0
		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
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)


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)
		exit()
	else:
		mid.append(memo)
else:
	check = 0
	for moji in dic:
		if len(dic[moji]) % 2 == 1:
			print(-1)
			exit()
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
BIT = [0] * (n + 1)

def BIT_query(idx):
	res_sum = 0
	while idx > 0:
		res_sum += BIT[idx]
		idx -= idx & -idx
	return res_sum

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)


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)


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)


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)


import sys

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

class BIT:

	def __init__(self, size):
		self.table = [0 for _ in range(size + 2)]
		self.size = size

	def Sum(self, 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)
	sys.exit()
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
(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
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
		elif 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(InversionNumber(to_sort_idx))
main()


from collections import Counter
S = input()
N = len(S)
apperance = Counter(S)
flag = False
for (k, v) in apperance.items():
	if v % 2 == 1:
		if flag:
			print(-1)
			exit()
		else:
			flag = True
			t = k
place = {}
for i in range(N):
	s = S[i]
	if s not in place:
		place[s] = []
	place[s].append(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)


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 = i + 1
		while i <= self.n:
			self.bit[i] += val
			i += i & -i

	def get_sum(self, 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)
			exit()
		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 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
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):
		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 = S()
n = len(s)
s_index = defaultdict(list)
for (i, x) in enumerate(s):
	s_index[x].append(i)
T = [0] * n
flag = False
AC = []
for (x, index_list) in s_index.items():
	count = len(index_list)
	if count % 2 == 1:
		if flag:
			print(-1)
			exit()
		else:
			flag = True
			mid = index_list[count // 2]
			T[mid] = n // 2
	for i in range(count // 2):
		a = index_list[i]
		c = index_list[-i - 1]
		AC.append((a, c))
AC.sort(key=itemgetter(0))
for (i, (a, c)) in enumerate(AC):
	T[a] = i
	T[c] = n - i - 1
BIT = BinaryIndexedTree(n)
inversion = 0
for (i, t) in enumerate(T):
	i += 1
	t += 1
	BIT.add(t, 1)
	inversion += i - BIT.sum(t)
print(inversion)


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)


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


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


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


import sys

def bitadd(a, w, bit):
	x = a
	while x <= len(bit) - 1:
		bit[x] += w
		x += x & -1 * x

def bitsum(a, bit):
	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 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 count.values():
	if v % 2 == 1:
		if flag:
			print(-1)
			exit()
		else:
			flag = True
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)


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)
count = Counter(S)
flag = False
for v in list(count.values()):
	if v % 2 == 1:
		if flag:
			print(-1)
			return
		else:
			flag = True
memo = [None] * N
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
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)


def main():
	from collections import deque

	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

		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

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

		def sum_range(self, i, j):
			return self.sum(j) - self.sum(i)

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


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):
		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=[]):
		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())


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)


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


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

class FenwickTree:

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

	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)

	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)


from collections import Counter

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 = i + 1
		while i <= self.n:
			self.bit[i] += val
			i += i & -i

	def get_sum(self, 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)
	exit()
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)


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


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
		self.laz = [self.ID_M] * (2 * self.N0)
		self.val = None

	def build(self, initial):
		self.val = initial[:]

	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)

	def thrust(self, k):
		for i in range(self.height, -1, -1):
			self.propagate(k >> i)

	def update(self, L, R, f):
		L += self.N0
		R += self.N0 + 1
		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

	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

	def point_set(self, k):
		self.thrust(k + self.N0)
		self.val[k] = x
import sys
readline = sys.stdin.readline
read = sys.stdin.read
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))
			if d < v:
				I = idx
				v = d
	seg.update(0, lst[I].popleft(), 1)
	seg.update(lst[I].pop(), n - 1, -1)
	ans += v
print(ans)


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


a2n = lambda x: ord(x) - ord('a')
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

class BIT:

	def __init__(self, n):
		self.n = n
		self.data = [0] * (n + 1)
		self.el = [0] * (n + 1)

	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

	def sumlr(self, i, j):
		return self.sum(j) - self.sum(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):
	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
		tmp += bit.sum(l)
		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 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()))


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import deque
S = [None] + [int(x) - ord('a') for x in read().rstrip()]

class BinaryIndexedTree:

	def __init__(self, seq):
		self.size = len(seq)
		self.depth = self.size.bit_length()
		self.build(seq)

	def build(self, seq):
		data = seq
		size = self.size
		for (i, x) in enumerate(data):
			j = i + (i & -i)
			if j < size:
				data[j] += data[i]
		self.data = data

	def __repr__(self):
		return self.data.__repr__()

	def get_sum(self, i):
		data = self.data
		s = 0
		while i:
			s += data[i]
			i -= i & -i
		return s

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

	def find_kth_element(self, k):
		data = self.data
		size = self.size
		(x, sx) = (0, 0)
		dx = 1 << self.depth
		for i in range(self.depth - 1, -1, -1):
			dx = 1 << i
			if x + dx >= size:
				continue
			y = x + dx
			sy = sx + data[y]
			if sy < k:
				(x, sx) = (y, sy)
		return x + 1
N = len(S) - 1
close = [False] * (N + 1)
x_to_I = [deque() for _ in range(26)]
for (i, x) in enumerate(S[1:], 1):
	x_to_I[x].append(i)
counter = [len(I) for I in x_to_I]
odd_cnt = sum((x & 1 for x in counter))
if odd_cnt >= 2:
	print(-1)
	exit()
find_center = False
bit = BinaryIndexedTree([0] * (N + 1))
answer = 0
for r in range(N, 0, -1):
	x = S[r]
	bl = close[r]
	if bl:
		continue
	l = x_to_I[x][0]
	if l == r:
		find_center = True
		continue
	x_to_I[x].pop()
	x_to_I[x].popleft()
	costR = 1 if find_center else 0
	costL = l - 1 - bit.get_sum(l)
	bit.add(l, 1)
	bit.add(r, 1)
	close[l] = True
	answer += costL + costR
print(answer)