前置知识：前缀和，单调栈，线段树上二分。

对原序列进行一个处理，将 p 当成 $1$，j 当成 $-1$，进行前缀和，设前缀和数组为 $a_i$。

对于一个满足题目条件的区间 $[l,r]$，$l$、$r$ 显然满足：

• $a_{l-1} \le \min_{i=l}^{r} a_i$

• $a_{r} \ge \max_{i=l}^{r} a_i$

扫一遍 $a$ 来枚举 $l-1$，找出最大的 $r$，满足上述两个限制，即 $a_{l-1}$ 小于等于区间 $[l-1,r]$ 最小值，$a_{r}$ 为区间 $[l,r]$ 最大值。

设当前扫到的位置是 $i$。考虑第一个限制怎么满足。设满足该限制的最远的点下标为 $lim$，发现 $lim$ 具有单调性（若 $lim$ 满足该限制，则 $lim-1$ 也一定满足该限制），可以使用线段树上二分。

线段树上二分大概的具体过程：

维护一个支持区间求 $min$ 的线段树，所有点初始值为 $inf$。

修改正常写。查询的时候，设当前线段树节点为 $p$，当前节点的左儿子为 $ls$，当前节点的右儿子为 $rs$，区间维护的最小值为 $mn$，查询的值为 $val$。

当 $val \le tr[ls].mn$：说明 $val$ 是 $ls$ 维护区间的最小值了，故递归查询 $rs$；

否则，说明 $val$ 已经不是 $ls$ 维护区间的最小值，右端点不在 $ls$ 维护的区间内，递归查询 $ls$。

扫完一个点后，将它更新到线段树中。

因为所有点的初始值是 $inf$，所以保证了查询的时候 $i$ 之前的区间不对查询造成影响，最小只会查询到 $i$。

发现查询出的 $r$ 不一定满足第二个限制。怎么办？

考虑在扫的过程中，用单调栈维护满足第二个限制的 $r$。在扫到 $i$ 的时候，在单调栈中二分找出 $\le lim$ 的最大的 $r$。以 $i$ 为 $l-1$ 的最长符合题目条件的区间即为 $[i+1,r]$。扫的过程中，$ans$ 不断与算出的区间长度取 $max$ 即可。

注意 $l=1$ 的情况也要计算。

时间复杂度为 $O(n \log n)$，瓶颈在线段树上二分。

AC code：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1000004;
int n;
int a[maxn];
namespace Segtree{
	struct node{
		int l,r;
		int mn;
	}tr[maxn<<2];
	#define ls (p<<1)
	#define rs (p<<1|1)
	#define mid (tr[p].l+tr[p].r>>1)
	void build(int p,int l,int r){
		tr[p].l=l,tr[p].r=r;
		tr[p].mn=maxn;
		if(l==r) return;
		build(ls,l,mid);build(rs,mid+1,r);
	}
	void upd(int p,int loc,int val){
		tr[p].mn=min(tr[p].mn,val);
		if(tr[p].l==tr[p].r) return;
		if(loc<=mid) upd(ls,loc,val);
		else upd(rs,loc,val);
	}
	int qry(int p,int val){//到最远哪个点还是min 
		if(tr[p].l==tr[p].r){
			if(tr[p].mn<val) return tr[p].l-1;//到单个点的时候val仍然不是最小值，返回原区间-1
			return tr[p].l;
		}
		if(val>tr[ls].mn) return qry(ls,val);
		else return qry(rs,val);
	}
}using namespace Segtree;
int stk[maxn],tp;
int bs(int x){
	int l=1,r=tp+1,md;
	stk[r]=0;
	while(l<r){
		md=l+r>>1;
		if(stk[md]<=x) r=md;
		else l=md+1;
	}
	return stk[l];
}//单调栈中二分
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n;
	char c;
	for(int i=1;i<=n;i++){
		cin>>c;
		if(c=='p') a[i]=1;
		else a[i]=-1;
		a[i]+=a[i-1];
	}
	build(1,1,n);
	a[0]=maxn+528;//确保弹栈时不会弹空栈
	int ans=0;
	for(int i=n;i>=1;i--){
		int to=qry(1,a[i]);//lim
		to=bs(to);//满足条件的最大r
		if(!to) to=i;
		ans=max(ans,to-i);//求答案
		while(a[i]>a[stk[tp]]) tp--;
		stk[++tp]=i;//维护单调栈
		upd(1,i,a[i]);//更新线段树
	}
	int to=qry(1,0);
	to=bs(to);//特别处理区间为[1,r]的情况
	ans=max(ans,to);
	cout<<ans<<'\n';
	return 0;
}