Minimizing Maximum Dissatisfaction in Toilet Queue Reordering

After a contest, 2N contestants line up to use two toilets before lunch. One toilet is exclusively for females and the other is a unisex toilet. The number of males and females may differ. The rules for entering the stalls are as follows:

• If the person at the head of the line is a female, she can enter if any toilet is available. If both toilets are available, she will choose the female‐only toilet.
• If the person at the head is a male, he can only enter if the unisex toilet is available. However, if only the female‐only toilet is available, then the female who is closest to the head of the queue may bypass her place and use the toilet immediately.

Every contestant takes exactly 1 minute to use the toilet and switching times are neglected. There are exactly N minutes available before lunch, and in each minute both toilets can be used concurrently (one person per toilet), so all 2N contestants must be served within that time.

The organizers are allowed to reorder the queue arbitrarily. However, some contestants may get displeased if they are delayed relative to their original position. The dissatisfaction of a contestant is defined as the number of positions they have been moved backwards compared to the original queue (if a contestant’s new position is earlier than in the original queue, their dissatisfaction is 0).

The task is to determine the minimum possible maximum dissatisfaction among all contestants when a reordering is chosen so that the serving rules (and toilet restrictions) are satisfied and all contestants finish in time.

Note that:

• The female‐only toilet can only be used by females. It will be used in every minute (i.e. exactly N times) and must be assigned to a female each time.
• The unisex toilet will be used exactly N times and can be used by males or females. However, since males can only use the unisex toilet, at most one male can be served in a minute. Hence, if there are M males (with M ≤ N), then exactly M males must use the unisex toilet, and the remaining N − M slots of the unisex toilet will be occupied by females.

The original queue is given as a string of length 2N consisting of the characters F (female) and M (male), where the i-th character (1-indexed) represents the gender of the contestant at position i in the original queue.

Your task is to output a single integer — the minimal possible maximum dissatisfaction among all contestants, assuming an optimal reordering exists. It is guaranteed that the input will be such that a valid reordering exists (number of females ≥ N and number of males ≤ N).

Mathematical formulation: Find the minimum d such that there exists a permutation of the contestants into positions 1 through 2N satisfying:

• Positions 1 to N (female‐only toilet) are assigned to females, and positions N+1 to 2N (unisex toilet) are assigned exactly M males and N − M females.
• For each contestant originally at position i assigned to a new position j, we have
  \( \max(j - i, \, 0) \le d \).

inputFormat

The input consists of two lines:

1. An integer N (1 ≤ N ≤ 10⁵), representing the number of minutes (and hence the number of uses for each toilet).
2. A string of length 2N consisting only of characters F and M representing the genders of the contestants in the original queue order. It is guaranteed that the number of females is at least N and the number of males is at most N.

outputFormat

Output a single integer — the minimized maximum dissatisfaction achievable through an optimal reordering of the contestants.

sample

2
FFMM

0

</p>