#2430. 「POI2014」沙拉餐厅 Salad Bar

内存限制:128 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: vincent163

题目描述

译自 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 .