记录编号	577636	评测结果	AAAAAAAAAA
题目名称	3789.回文串回文	最终得分	100
用户昵称	yrtiop	是否通过	通过
代码语言	C++	运行时间	0.425 s
提交时间	2022-11-16 20:39:14	内存使用	5.46 MiB

// Problem: E - Papple Sort
// Contest: AtCoder - AtCoder Regular Contest 088
// URL: https://atcoder.jp/contests/arc088/tasks/arc088_c
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using i64 = long long;

const int maxn = 1e6 + 5;
char s[maxn];
int n,c[maxn],a[maxn];
std::list<int> G[50];
i64 ans;

int lowbit(int x) {
	return x & -x;
}

void add(int x,int y) {
	for(;x <= n;x += lowbit(x))c[x] += y;
	return ;
}

int query(int x) {
	int ans = 0;
	for(;x;x -= lowbit(x))ans += c[x];
	return ans;
}

int main() {
	freopen("strts.in","r",stdin);
	freopen("strts.out","w",stdout);
	scanf("%s",s + 1);
	n = strlen(s + 1);
	
	for(int i = 1;i <= n;++ i) {
		s[i] -= 'a';
		G[s[i]].emplace_back(i);
	}
	
	int cnt = 0;
	for(int i = 0;i < 26;++ i)
		cnt += G[i].size() & 1;
	if(cnt > 1) {
		puts("-1");
		return 0;
	}
	
	cnt = 0;
	for(int i = 1;i <= n;++ i) {
		if(a[i])continue ;
		if(G[s[i]].size() == 1)continue ;
		if((n & 1)&&cnt + 1 == (n + 1) / 2)++ cnt;
		a[i] = ++ cnt;
		G[s[i]].pop_front();
		a[G[s[i]].back()] = n - cnt + 1;
		G[s[i]].pop_back();
	}
	if(n & 1)
		for(int i = 1;i <= n;++ i)
			if(!a[i])
				a[i] = (n + 1) >> 1;
	
	for(int i = 1;i <= n;++ i) {
		ans += i - 1 - query(a[i]);
		add(a[i] , 1);
	}
	
	printf("%lld\n",ans);
	return 0;
}