회문

Farmer John의 연합 소 팀(UCFJ)이 연례 후프볼 선수권 대회에 참가했다. UCFJ 팀의 소 $N$마리 $(1 \le N \le 7500)$가 후프볼에서 금메달을 땄다. 아슬아슬한 차이로 Farmer Nhoj 팀을 제쳤다.

소들은 이미 시상식을 위해 줄을 섰다. 그들은 FJ에게 줄의 연속 부분 수열마다 한 장씩, 총 $\frac{N(N+1)}{2}$장의 단체 사진을 찍어 달라고 한다.

팀 코치인 FJ는 소를 세우는 방식에 까다롭다. 부분 수열이 회문이 아니면 사진을 찍지 않는다. 회문은 부분 수열의 길이까지의 모든 양의 정수 $i$에 대해, 왼쪽 끝에서 $i$번째 소의 품종이 오른쪽 끝에서 $i$번째 소의 품종과 같은 것을 말한다. 각 소의 품종은 Guernsey 또는 Holstein 중 하나다.

각 연속 부분 수열마다, 회문으로 재배열하는 데 필요한 자리 바꿈 횟수의 최솟값을 구한다. 회문을 만들 수 없으면 -1이다. 자리 바꿈은 부분 수열에서 인접한 두 소의 위치를 서로 맞바꾸는 것이다. 각 부분 수열은 독립적으로 계산하며, 사진을 찍을 때마다 소들은 원래 위치로 돌아간다. 이 값들의 합을 출력한다.

G와 H로 이루어진 길이 $N$의 문자열이 한 줄로 주어진다.

모든 $\frac{N(N+1)}{2}$개의 연속 부분 수열에 대해 위에서 구한 값의 합을 출력한다. 회문을 만들 수 없는 경우는 -1을 더한다.

처음 네 개의 연속 부분 수열은 G, GH, GHH, GHHG이다. G와 GHHG는 이미 회문이므로 0을 더한다. GHH는 자리 바꿈 한 번으로 회문을 만들 수 있어 1을 더한다. GH는 회문으로 재배열할 수 없어 -1을 더한다. 합에 기여하는 다른 부분 수열은 HHGG이다. 이 수열은 자리 바꿈 두 번으로 회문을 만들 수 있다.