Lanterns with One Repair#13115
There are houses arranged in a circle, numbered from to . One lantern stands next to each house.
Each lantern illuminates exactly one of the two neighboring houses:
L — the house on its left;
R — the house on its right.
A lantern does not illuminate the house it stands next to. The left neighbor of house is house i-1, and its right neighbor is house i+1. For house , the left neighbor is house ; for house , the right neighbor is house .
You may turn around at most one lantern, changing its direction from L to R or vice versa.
Find the maximum number of houses that can be illuminated by exactly one lantern afterwards.
The first line contains an integer (3\le n\le2\cdot10^5) — the number of houses.
The second line contains a string of length consisting of L and R. Character s_i gives the direction of the lantern next to house .
Print one integer — the maximum possible number of houses illuminated by exactly one lantern.
Example 1
Example 2
Example 3
In the first example, turn around the second lantern to obtain RRRRR. Every house is then illuminated by exactly one lantern, so the answer is .
In the second example, houses and initially receive light from two lanterns each, while houses and receive none. Turning around the first lantern makes houses and illuminated by exactly one lantern each. More than two such houses cannot be obtained.
In the third example, all four houses are already illuminated by exactly one lantern, so no change is needed.
Subtask ( points): n\le100.
Subtask ( points): n\le2000.
Subtask ( points): no additional constraints.