Maximizing the Cumulative Sum in a Monotonic Queue Algorithm

You are given a positive integer \(n\), an array \(c = [c_1, c_2, \dots, c_n]\) (which may contain negative numbers), and a permutation \(a = [a_1, a_2, \dots, a_n]\) of \(\{1,2,\dots,n\}\). Consider the following procedure that processes an increasing sequence of indices using a monotonic deque:

deque Q;
// Define l[0] = r[0] = 0 and sum = 0
for (int i = 1; i <= n; i++) {
    // Process new indices from r[i-1]+1 to r[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);
    }
    // Remove indices which are no longer in the current window
    while (Q.front() < l[i]) Q.pop_front();
    b[i] = Q.front();
}

The arrays \(l = [l_1, l_2, \dots, l_n]\) and \(r = [r_1, r_2, \dots, r_n]\) represent n intervals \([l_i, r_i]\) with the restrictions:

• \(1 \le l_i \le r_i \le n\),
• \(l_1 \le l_2 \le \cdots \le l_n\), and
• \(r_1 \le r_2 \le \cdots \le r_n\).

While the original problem was to compute, for each interval, the position of the maximum element in \(a_{l_i \sim r_i}\), here you are interested in the value of sum after the algorithm finishes. In the algorithm above, every time an element is popped from the back of the deque (because a newly processed element \(a[j]\) is greater than it), its corresponding cost \(c[\text{that index}]\) is added to sum. Note that indices removed from the front (when they fall out of the interval) do not contribute to sum.

Your task is to choose the intervals \([l_i, r_i]\) (for \(1 \le i \le n\)) satisfying the conditions so that when the above algorithm is executed the final value of sum is maximized. Equivalently, you are allowed to choose any valid combination of \(n\) intervals and you want to determine the maximum possible value of sum.

Observation: The algorithm processes indices in increasing order. Every index is pushed exactly once. An element is added to sum if it is removed from the deque by the inner loop, while elements that remain at the end (or are removed from the front due to window adjustment) do not contribute. Therefore, if an interval (segment) processes a contiguous block of indices \(S = \{j, j+1, \dots, i\}\), then the algorithm will eventually pop all elements except for the one corresponding to the maximum \(a\) value in that block. Thus, the contribution of such a segment is: \[ \Bigl(\sum_{p=j}^{i} c_p\Bigr) - c_{k}, \quad \text{where } k \text{ is the index with } \max\{a_p: j \le p \le i\}. \] You may choose not to process all indices (i.e. decide a prefix of \(\{1,2,\dots,n\}\) to process) so that segments with a negative removal penalty are avoided.

Formally, if you partition a chosen prefix \(1 \ldots k\) into segments, the final sum will be \[ \sum_{\text{segment }S}\Bigl(\sum_{p \in S} c_p - c_{\mathrm{argmax}_{p \in S} \; a_p}\Bigr). \] Determine the maximum possible sum over all valid choices of intervals.

inputFormat

The first line contains a single integer \(n\) \( (1 \le n \le 2000)\), the number of elements.

The second line contains \(n\) integers \(c_1, c_2, \dots, c_n\) (\(|c_i| \le 10^9\)).

The third line contains \(n\) integers \(a_1, a_2, \dots, a_n\), a permutation of \(\{1, 2, \dots, n\}\).

outputFormat

Output a single integer, the maximum possible value of sum after running the algorithm on some valid combination of intervals.

sample

3
1 2 3
2 1 3

3