Ianine's Soldier Problem
Disclaimer: This was copied directly from Mr. Ianine's email.
The general is standing in front of the army of \(N\) soldiers. The entire army is lined up in one row and each soldier faces the general. The general shouts "Turn", and each soldier immediately turns either 90 degrees to the right relative to the general or 90 degrees to the left relative to the general. Unfortunately, each soldier choose the direction of turn as random, so there is a good chance that there are pairs of soldiers facing each other.
In each pair of soldiers facing each other, both soldiers realize that they turned incorrectly and each of them makes a 180 degrees turn. Then if there are still pairs of soldiers facing each other, each soldier in each pair will make a 180 degrees turn. Each 180 degree turn takes 1 second.
Here how it goes:
- 1st second: All pairs facing each other with turn around
- 2nd second: All newly formed pairs facing each other will turn around
- 3rd second: All newly formed pairs facing each other will turn around
An integer \(N\) \((1 \le N \le 10^5)\), the number of soldiers, followed by a string representing the initial state of the soldiers.
Find the amount of time, in seconds, it will take the army to stop turning.