Description

Bytea went to a salad bar.

There are $n$ fruits lined up on the bar counter.

Specifically, these are apples and oranges.

Bytea can pick any contiguous segment of the line of fruits for her salad.

The fruits she chooses will be added to the salad either from left to right or from right to left.

As Bytea loves oranges, she requires that throughout the salad-making process, the number of oranges in the salad should always be no smaller than the number of apples, regardless of whether the fruits are added from left to right or from right to left.

Help Bytea by writing a program that finds the longest contiguous segment of the line of fruits that satisfies her requirements.

Input Format

The first line of the standard input contains a single integer $n$ ($1 \le n \le 1\ 000\ 000$), denoting the number of fruits.

The next line contains a string of $n$ characters $a_1, a_2, \cdots, a_n$ ($a_i \in \{j, p\}$).

These stand for Polish names of apples and oranges: jab\l{ka} and pomara'ncze.

Consequently, if $a_i = j$, then the $i$-th fruit in the line is an apple, and otherwise it is an orange.

Output Format

The first and only line of the standard output should contain a single integer equal to the number of fruits in the longest contiguous segment that satisfies Bytea's requirements.

Note that it could be the case that $0$ is the correct result.

6
jpjppj

4

Hint

Given a string of length $n$ consisting only of 'p' and 'j', find the longest substring such that, whether you take it from left to right or from right to left, at every moment the number of 'p' taken is no less than the number of 'j'.

Translated by ChatGPT 5