题目背景

原题链接：https://oier.team/problems/S7C。

题目描述

给定一个正整数 $n$ 和 $n$ 个整数 $c_1, \ldots, c_n$（这些数可能为负），以及一个 $1 \sim n$ 的排列 $(a_1, \ldots, a_n)$。

为了考验朋友小 L 的能力，你设计了一道这样一道题目：

给定 $n$ 个区间 $[l_1, r_1], [l_2, r_2], \dots, [l_n, r_n]$，它们满足以下条件：

• $1 \leq l_i \leq r_i \leq n$；
• $l_1 \leq l_2 \leq \dots \leq l_n$；
• $r_1 \leq r_2 \leq \dots \leq r_n$。

对于每个区间 $[l_i, r_i]$，小 L 需要求出 $a_{l_i \sim r_i}$ 中最大值的位置，记为 $b_i$。

小 L 准备使用单调队列来高效地完成这个题目。他的算法核心伪代码如下：

---

---

对应的 C++ 实现代码如下：

deque<int> Q;
l[0] = r[0] = sum = 0;
for (int i = 1; i <= n; i++) {
    for (int j = r[i - 1] + 1; j <= r[i]; j++) {
        while (!Q.empty() && a[Q.back()] < a[j]) {
            sum = sum + c[Q.back()];
            Q.pop_back();
        }
        Q.push_back(j);
    }
    while (Q.front() < l[i]) Q.pop_front();
    b[i] = Q.front();
}

你发现小 L 一遍就通过了这道题目，但是你突然对 sum 的值非常感兴趣。现在你想知道，在所有满足条件的 $n$ 个区间的组合中，算法结束后 sum 的最大值是多少。

输入格式

第一行，一个正整数 $n$。

第二行，$n$ 个整数 $c_1, \ldots, c_n$。

第三行，$n$ 个正整数 $a_1, \ldots, a_n$，保证 $(a_1, \ldots, a_n)$ 为 $1 \sim n$ 的排列。

输出格式

仅一行，一个整数，表示答案。

5
-190 133 210 155 -442
1 3 2 4 5

308

10
-205 -268 -487 -112 -82 -330 153 133 -219 -157
5 6 7 9 2 1 4 10 3 8

0

5
-288 479 205 -310 -66
1 3 2 4 5

396

提示

【样例解释 #1】

若所有区间都为 $[5,5]$，则算法结束后 sum 的值为 $308$。可以证明没有使 sum 更大的方案。

【样例解释 #2】

若所有区间都为 $[1,1]$，则算法结束后 sum 的值为 $0$。可以证明没有使 sum 更大的方案。

【样例解释 #3】

若 $5$ 个区间分别为 $[2,2]$、$[2,2]$、$[2,4]$、$[2,4]$、$[2,4]$，则算法结束后 sum 的值为 $396$。可以证明没有使 sum 更大的方案。

【样例 #4】

见附件中的 queue/queue4.in 与 queue/queue4.ans。

该组样例满足测试点 $2\sim 5$ 的约束条件。

【样例 #5】

见附件中的 queue/queue5.in 与 queue/queue5.ans。

该组样例满足测试点 $8\sim 12$ 的约束条件。

【样例 #6】

见附件中的 queue/queue6.in 与 queue/queue6.ans。

该组样例满足测试点 $15\sim 16$ 的约束条件。

【数据范围】

对于所有测试数据，保证：$2\le n\le 5\times 10^5$，$\lvert c_i \rvert\le 10^9$，$1 \le a_i \le n$，$(a_1, \ldots, a_n)$ 为 $1\sim n$ 的排列。

测试点编号	$n\le$	特殊性质
$1$	$6$	无
$2\sim 5$	$15$
$6\sim 7$	$5\times 10^5$	A
$8\sim 12$	$5000$	无
$13\sim 14$	$2\times 10^5$	B
$15\sim 16$		C
$17\sim 19$	$10^5$	无
$20\sim 25$	$5\times 10^5$

• 特殊性质 A：满足 $c_i > 0$ 的 $i$ 不超过 $1$ 个。
• 特殊性质 B：满足 $c_i < 0$ 的 $i$ 不超过 $2$ 个。
• 特殊性质 C：满足 $c_i < 0$ 的 $i$ 不超过 $10$ 个。