树形 DP。

对于排列中的某一个位置 $y$，我们设 $x$ 是最大的满足 $x \lt y$ 且 $a_x \gt a_y$ 的位置。特别的，如果不存在这样的 $x$，则令 $x$ 为 $0$。$x$ 容易用单调栈求出。

容易发现，如果 $x$ 被从单调队列的队尾弹出，而不是队头，那么 $y$ 也一定是被从单调队列的队尾弹出。

然后，我们把 $y$ 在树上的父亲设为 $x$，就得到了一棵 $n+1$ 个节点的树。

例如，对于样例 $2$，我们建出来的树长这样：

这棵树存在这样的性质：如果某个点对答案造成了贡献，则以该点为根的子树里的所有的点都对答案造成了贡献。

但是，叶节点是特殊的。首先，由题可知，单调队列一旦被从队尾删空，就一定会加入一个新的点，使得队列非空。另外，类似样例 $2$，并不是所有的点都会被加入单调队列，只有一个前缀会被加入。

根据以上两点，叶节点对答案造成的贡献有这样的规则：存在一个整数 $k$，所有编号小于等于 $k$ 的叶节点都对答案造成贡献，所有编号大于 $k$ 的叶节点都不对答案造成贡献。

此外，最右侧的链由于到结束也还在单调队列中，也没法对答案造成贡献。

例如对于上图，可能的对答案造成贡献的组合只有以下几种：

1
1 2
1 2 3
1 2 3 6 5
1 2 3 6 5 7 4
1 2 3 6 5 7 4 9
1 2 3 6 5 7
1 2 3 6 5 7 9
1 2 3 6
1 2 3 6 7
1 2 3 6 7 9

于是，我们有了一个树形 DP。

设 $f_x$ 为以 $x$ 为根的子树，叶节点必须都选的最大的 $c$ 之和，$g_x$ 为以 $x$ 为根的子树，有一半叶节点选则，有一半叶节点不选的最大的 $c$ 之和。

如果不选 $x$，对于 $x$ 的每个子节点 $y$，有转移 $\begin{cases}g_x \gets \max \{g_x, f_x + g_y \} \\ f_x \gets \max \{f_x, f_x + f_y \} \end{cases}$。 注意有先后顺序。

如果选 $x$，则有 $\begin{cases}g_x \gets \max \{g_x, \sum_{y \in \texttt{subtree}_x} c_y \} \\ f_x \gets \max \{f_x, \sum_{y \in \texttt{subtree}_x} c_y \} \end{cases}$。

时间复杂度 $O(n)$。

代码很短：

#include<bits/stdc++.h>
#define LL long long
#define Maxn 500005
using namespace std;
int n,a[Maxn],c[Maxn];
stack<int> q;
vector<int> e[Maxn];
LL f[Maxn],g[Maxn],all[Maxn];

void dfs(int x){
	all[x] = c[x];
	if(e[x].empty()){
		f[x] = c[x];
		g[x] = max(0, c[x]);
		return;
	}
	for(int y : e[x]){
		dfs(y);
		all[x] += all[y];
		g[x] = max(g[x], f[x] + g[y]);
		f[x] += f[y];
	}
	f[x] = max(f[x], all[x]);
	g[x] = max(g[x], all[x]);
}

int main(){
	scanf("%d",&n);
	for(int i=1; i<=n; i++) scanf("%d",c+i);
	for(int i=1; i<=n; i++) scanf("%d",a+i);
	
	q.emplace(0);
	for(int i=1; i<=n; i++){
		while(q.size() > 1 && a[q.top()] <= a[i]){
			q.pop();
		}
		e[q.top()].emplace_back(i);
		q.emplace(i);
	}
	while(!q.empty()){
		c[q.top()] = 0; q.pop();
	}
	
	dfs(0);
	printf("%lld\n", g[0]);
	return 0;
}