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. Kaitlyn doesn't have a lot of time so in a single operation, she can pick up one magnet and put it between any two adjacent magnets on the fridge or at either end.
Compute the minimum number of operations Kaitlyn needs to make this happen.
~1 \le N \le 10^5~
In tests worth 1 mark, ~N \le 10~.
In tests worth an additional 4 marks, ~N \le 10^3~.
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
Output an integer ~X~, the minimum number of operations needed to rearrange the magnets as desired. If it is impossible to do so, output