Description

There is a sequence. You may delete, any number of times, a contiguous segment that meets the rules below. Each deletion yields a score equal to the length of that segment.

The segment must satisfy:

1. For every pair of adjacent elements, the absolute difference is $1$.
2. If an element is not the leftmost or rightmost element of the segment, then it cannot be strictly smaller than both of its immediate neighbors.

All of $[1,2,3,4,3]$, $[1,2]$, $[3,2]$, and $[3]$ satisfy the rules.

After removing a segment, the elements to the left and right of that segment become adjacent.

Your task is: for the given sequence, compute the maximum possible total score.

Input Format

The first line contains an integer $N$, the length of the sequence.

The second line contains $N$ integers $V_1, V_2 \cdots V_N$, where $V_L$ is the score for deleting a segment of length $L$.

The third line contains $N$ integers $A_1, A_2 \cdots A_N$, the elements of the initial sequence.

Output Format

Output a single integer: the maximum total score that can be obtained.

6
-100 5 6 10 0 0
3 1 2 3 4 10

11

Hint

Constraints

• For $10\%$ of the testdata, $N \le 3$.
• For $40\%$ of the testdata, $N \le 10$.
• For $70\%$ of the testdata, $N \le 70$.
• For $100\%$ of the testdata, $1 \le N \le 150$, $-10000 \le V_i \le 10000$, $0 \le A_i \le 1000000000$. No value $A_i$ appears more than $14$ times.

Translated by ChatGPT 5