Salad Bar

Interview

Time limit3sMemory limit256 MB

Summary

Find the longest contiguous block of apples and oranges where oranges never fall behind apples when added from either end.

Level: Medium5 of 10
Topics: Prefix sum, Stack, Array
Solved: No attempts yet

Problem

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.

Input

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.

Output

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

Examples1

Example 1
Input
```
6
jpjppj
```
Expected output
```
4
```