题目描述

译自 POI 2014 Stage 1.「Salad Bar」

桌面上有 $n$ 个水果，分别是苹果和橘子。Bytesar 需要从水果中选择连续的一个区间，并从左到右或从右到左拿水果，且两个过程中橘子的数量必须始终不小于苹果的数量。求最长的区间大小。

输入格式

第一行一个整数 $n$（$1 \le n \le 10^6$），表示水果个数。 接下来一行共有 $n$ 个字符$a_1, a_2, ..., a_n (a_i \in \{j,p\})$，分别表示苹果和橘子（波兰语）。

输出格式

输出一行共一个数字，表示最长的区间大小。

样例

6
jpjppj

4

数据范围与提示

对于 $20\%$ 的数据，$n \le 10^3$.
对于 $50\%$ 的数据，$n \le 10^4$.
对于所有数据，$1 \le n \le 10^6$.