题目描述

Bytea 去了一间沙拉自助吧台。

吧台上有一排 $n$ 个水果。

具体来说，水果只有苹果和橙子。

Bytea 可以选取水果序列中任意一段连续区间来制作沙拉。

她选中这段水果后，有两种依次添加进沙拉的顺序：从左往右，或是从右往左。

Bytea 很爱吃橙子，因此她提出要求：无论采用哪种添加顺序，在整个往沙拉里放水果的全过程中，沙拉里橙子的数量每时每刻都不能少于苹果的数量。

请你编写程序，帮 Bytea 找出满足上述全部条件的、长度最长的连续水果区间。

输入格式

标准输入的第一行包含一个整数 $n$（$1 \le n \le 10^6$），代表水果的总数。

下一行给出一个长度为 $n$ 的字符串，其字符为 $a_1, a_2, \cdots, a_n$ ($a_i \in \{j, p\}$)。

这两个字符对应苹果与橙子的波兰语名称：jabłka（苹果）和 pomarańcze（橙子）。

若 $a_i = j$，则第 $i$ 个水果为苹果，否则为橙子。

输出格式

标准输出仅有一行，该行需输出一个整数，表示满足 Bytea 所有要求的最长连续水果区间包含的水果数量。

注意答案有可能为 $0$。

6
jpjppj

4

提示

简要题意：

有一个长度为 $n$ 的字符串，每一位只会是 $p$ 或 $j$。求一个最长子串，使得不管是从左往右还是从右往左取，都保证每时每刻已取出的 $p$ 的个数不小于 $j$ 的个数。