Salad Bar

Bytea visits a salad bar with $n$ fruits in a row. Each fruit is an apple or an orange.

She may choose any contiguous block of fruits. The block is added to the salad either from left to right or from right to left. While fruits are added, the count of oranges must never be smaller than the count of apples, no matter which direction is used.

Find the maximum length of a contiguous block that satisfies this rule.

The first line contains an integer $n$ ($1 \le n \le 1\,000\,000$), the number of fruits.

The second line contains a string of length $n$ over the alphabet $\{j, p\}$. Character $j$ means apple and $p$ means orange.

Print one integer, the maximum length of a valid contiguous block. The answer may be $0$.