Mock CCC '22 S2 - IU

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 0.25s
Memory limit: 1G

Problem type

Kaitlyn is the world's biggest IU fan. One day, she is bored and buys 2N magnets. N of them have the letter I on them and N of them have the letter U on them. She arranges them on the fridge to spell IU repeated N times.

Sadly, her archnemesis, Sylvia, has broken into her apartment and rearranged the magnets because she is not an IU fan.

Kaitlyn wants to fix the magnets so that it spells IU repeatedly. However, Kaitlyn is tired, so the only operation she can do is swap two adjacent magnets.

Compute the minimum number of operations Kaitlyn needs to make this happen.


1 \le N \le 10^6

In tests worth 1 mark, N \le 10.

In tests worth an additional 4 marks, N \le 10^3.

Input Specification

The first line contains a single integer N.

The second line contains a string of 2N characters. It is guaranteed that N of them are I and N of them are U.

Output Specification

Output an integer X, the minimum number of operations needed to rearrange the magnets as desired. If it is impossible to do so, output -1.

Sample Input


Sample Output



There are no comments at the moment.