Beaver Chorus Partitioning

On a stage, there are (2N) beavers standing in a row. Each beaver sings either the alto part (represented by the character A) or the bass part (represented by the character B). It is known that exactly (N) beavers sing the alto part and (N) beavers sing the bass part. From the stage‐right (i.e. the leftmost beaver when seen from the audience) the order of beavers is given by the string (S) of length (2N) (1-indexed).

They are going to sing (K) songs. However, every beaver sings exactly one song. For each song the following conditions must be met:

1. At least one beaver sings the song.
   
2. The number of beavers singing the alto part is equal to the number of beavers singing the bass part.
   
3. If we consider only the beavers singing that song (in the order of their positions from stage‐right to stage‐left), then every alto beaver must stand on the stage‐right of every bass beaver. In other words, if in that song you list the positions of the participating beavers in increasing order, then all the A’s appear before all the B’s.
   
   Bitaro, the conductor, wishes to reassign songs to the beavers so that the above conditions are satisfied. However, he is allowed only to swap adjacent beavers (an operation that counts as one move) in order to change their order. He wants to know the minimum number of adjacent swaps necessary so that there exists some way to allot the (K) songs (each song will receive a nonempty group) satisfying the conditions.
   
   Note that when (K = 1) the entire sequence must be transformed into the form A^(N)B^(N) (i.e. all the altos on the stage‐right and then all the basses), while if (K) is larger (with (1 \le K \le N)) then the row is required to be partitionable into (K) contiguous blocks, each of even length (2r) (with (r\ge1)) and of the form [ \underbrace{A\cdots A}{r} ;\underbrace{B\cdots B}{r} ] (which then can be allocated as one song).
   
   Your task is to compute the minimum number of adjacent swap operations needed so that the beavers can be rearranged into an order which admits a partition into exactly (K) segments (each with at least one A and one B arranged as described) covering the whole row.

inputFormat

The input consists of two lines. The first line contains a single integer (K) (with (1 \le K \le N)). The second line contains the string (S) of length (2N) consisting only of the characters A and B. It is guaranteed that (S) contains exactly (N) A's and (N) B's.

outputFormat

Output a single integer — the minimum number of adjacent swap operations required so that the beavers can be rearranged into an order which allows an allocation into (K) songs satisfying the conditions.

sample

1
AABB

0