샐러드 바

면접 대비

시간 제한3초메모리 제한256 MB

요약

사과와 오렌지가 일렬로 놓일 때 어느 한쪽 끝에서부터 담아도 오렌지가 사과보다 적어지지 않는 가장 긴 연속 구간을 구합니다.

문제

바이테아가 샐러드 바에 갔습니다. 카운터 위에 $n$ 개의 과일이 한 줄로 놓여 있고, 각 과일은 사과 또는 오렌지입니다.

연속한 구간을 골라 샐러드를 만들 때, 왼쪽에서 오른쪽으로 넣거나 오른쪽에서 왼쪽으로 넣을 수 있습니다. 어느 방향이든 과일을 넣는 동안 오렌지 개수는 항상 사과 개수 이상이어야 합니다.

이 조건을 만족하는 연속 구간의 최대 길이를 구하세요.

첫 줄에 정수 $n$ ( $1 \le n \le 1\,000\,000$ )이 주어집니다.

둘째 줄에 길이 $n$ 의 문자열이 주어집니다. 문자 $j$ 는 사과, $p$ 는 오렌지를 뜻합니다.

조건을 만족하는 연속 구간의 최대 길이를 한 줄에 출력합니다. 답이 0일 수 있습니다.