Emma and the Strange Circle#10222
After winning one of the world's most prestigious film awards, Emma received a rather unusual gift—a circle divided into sectors. The circle has an even number of sectors, denoted as . Some sectors contain stones, while others are empty.
Emma noticed that she can move a stone only to the sector directly opposite. However, it is not possible to place two stones in one sector (do not ask why or how—it is magic). Since the party after the award ceremony turned out to be rather boring, Emma decided to figure out the length of the longest sequence of consecutive sectors filled with stones that she can obtain after any number of moves.
Emma is an actress, so your task is to help her with this puzzle.
Let us recall the rules for moving stones:
A stone can be moved only to the sector directly opposite.
There cannot be more than one stone in a sector.
For better understanding, the image shows one possible way to move the stones for the first sample test case.
The first line contains a single integer . The second line contains numbers: or ( means a stone is present in the sector, means the sector is empty). 1 \le n \le 10^6. is even. There is at least one empty sector.
Output a single integer—the length of the longest magical sequence (of consecutive filled sectors) that can be achieved.
Example 1
Example 2