1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<cstdio>
#include<cstring>
const int N=1000010,M=128;
int n,m,i,j,k,ap[M],vis[M],vip,g[M],nxt[N],bit[N];long long ans;char a[N],b[N];
int main(){
  scanf("%s",a+1);n=strlen(a+1);
  for(i=1;i<=n;i++)ap[a[i]]++;
  for(i=0;i<M;i++)if(ap[i]&1)vip++,k=i;
  if(vip>(n&1))return puts("-1"),0;
  for(i=1;i<=n;i++){
    vis[a[i]]++;
    if(vis[a[i]]*2<=ap[a[i]])b[++m]=a[i];
  }
  if(n&1)b[n/2+1]=k;
  for(i=1,j=n;i<j;i++,j--)b[j]=b[i];
  for(i=1;i<=n;i++){
    nxt[i]=g[a[i]];
    g[a[i]]=i;
  }
  for(i=n;i;i--){
    k=j=g[b[i]];
    for(g[b[i]]=nxt[g[b[i]]];k;k-=k&-k)ans+=bit[k];
    for(;j<=n;j+=j&-j)bit[j]++;
  }
  printf("%lld",ans);
}