Palindromic Rearrangement Swaps

UCFJ (The United Cows of Farmer John) won the annual hoofball tournament with their N cows (where $1\leq N\leq7500$), each of which is either a Guernsey (G) or a Holstein (H). For the award ceremony, the cows want to take a photograph for every contiguous subsegment (there are $\frac{N(N+1)}{2}$ subsegments). However, Farmer John insists that a photograph is taken only if the cows in the subsegment can be rearranged into a palindrome. A string is a palindrome if, for every positive integer $i\leq L$ (where $L$ is the length of the string), the $i$th cow from the left has the same breed as the $i$th cow from the right.

For each contiguous subsegment, determine the minimum number of adjacent swaps required to rearrange its cows into a palindrome. In a single swap you may swap two adjacent cows in the subsegment. If it is impossible to rearrange the subsegment into a palindrome, the cost is ( -1).

Note: The minimum swap count is computed independently for every subsegment (i.e. after each photograph the cows return to their original order).

(\text{Total Cost} = \sum_{\text{subsegment } S} \text{minSwaps}(S))

Below is an example of how the minimum adjacent swap algorithm works for a rearrangeable string:

function minSwaps(s):
    convert s to a list arr
    swaps = 0
    l = 0, r = len(arr)-1
    while l  l and arr[k] != arr[l]:
                k--
            if k == l: // then arr[l] is the pivot character for odd-length palindrome
                swap arr[l] and arr[l+1]
                swaps++
            else:
                while k < r:
                    swap arr[k] and arr[k+1]
                    swaps++
                    k++
                l++, r--
    return swaps

In this problem, you need to process all contiguous subsegments of the input string. For even-length subsegments, a palindrome is possible only if both breed counts are even; for odd-length subsegments, exactly one breed must appear an odd number of times. Your task is to output the sum of minimum swap counts (using ( -1 ) for subsegments that cannot form a palindrome) over all contiguous subsegments.

inputFormat

The first line contains an integer N ($1 \leq N \leq 7500$), the number of cows.

The second line contains a string of length N consisting only of the characters G and H, representing the cows' breeds.

outputFormat

Output a single integer: the sum over all contiguous subsegments of the minimum number of adjacent swaps needed to rearrange that subsegment into a palindrome, where a subsegment that cannot be rearranged is counted as \( -1 \).

sample

3
GHG

-2