Problem Description

JOI Island consists of $L$ districts, numbered from $1$ to $L$ from west to east. There are $(L - 1)$ roads on the island, numbered from $1$ to $L - 1$. Road $i$ ($1 \le i \le L - 1$) connects districts $i$ and $i + 1$ in both directions.

Now, IOI 20XX is planned to be held on JOI Island. However, there is a concern: JOI Island is famous for being a “stove”. The risk of heat stroke on the island is high, especially for foreigners who are not used to JOI Island’s hot climate. Therefore, the IOI organizers decide to take the following measures:

• For each $1 \le i \le L$, there is a hospital in district $i$ with capacity $C_i$ people. Note that $C_i$ can be $0$.

• During the IOI event, when a person suffers heat stroke on road $x$ ($1 \le x \le L - 1$), they will be taken to a hospital by the following procedure:

  • Take the person to a hospital in district $x$ or district $x + 1$ that is not full. If the hospitals in both districts are not full, either one may be chosen. If both hospitals are full, use a helicopter to take the person to a hospital outside the island.

Since using a helicopter is expensive, the organizers want to estimate the maximum possible number of patients who may need a helicopter. They consider the following situation:

• Before the IOI event, there are no patients in any hospital.
• During the IOI event, $N$ people will suffer heat stroke one by one. The $j$-th person ($1 \le j \le N$) suffers heat stroke on road $X_j$.
• For any $1 \le j \le N - 1$, when the $(j + 1)$-th person suffers heat stroke, persons $1, 2, \cdots, j$ have already arrived at hospitals. Since heat stroke is severe, nobody leaves the hospital during the IOI event.

You need to write a program. Given the number of districts, the hospital information, and the heat stroke information, compute the maximum possible number of patients who need a helicopter in the above situation.

Input Format

The input format is as follows:

$L$
$C_1$ $C_2$ $\cdots$ $C_L$
$N$
$X_1$ $X_2$ $\cdots$ $X_N$

Output Format

Output one line containing one integer, which is the maximum possible number of patients who need a helicopter.

3
1 1 1
3
1 2 2

1

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

3

6
4000 1 1 0 4000 1
5
1 1 2 3 5

1

5
1 2 2 2 1
8
2 3 2 1 4 1 2 3

2

10
2 2 2 2 2 2 2 2 2 2
18
1 3 5 7 9 2 4 6 8 1 3 5 7 9 2 4 6 8

3

Hint

Sample Explanation

For sample $1$, consider the following:

• Send the first patient to the hospital in district $2$. The numbers of patients in the hospitals of the three districts are then $0, 1, 0$.
• Send the second patient to the hospital in district $3$. The numbers of patients in the hospitals of the three districts are then $0, 1, 1$.
• For the third patient, since the hospitals in districts $2$ and $3$ are both full, the only option is to use a helicopter to take them off the island.

In this case, $1$ person is taken off the island by helicopter. It can be proven that this is the maximum.

For sample $2$, consider the following:

• Send the first patient to the hospital in district $2$. The numbers of patients in the hospitals of the six districts are then $0, 1, 0, 0, 0, 0$.
• Send the second patient to the hospital in district $4$. The numbers of patients in the hospitals of the six districts are then $0, 1, 0, 1, 0, 0$.
• Send the third patient to the hospital in district $5$. The numbers of patients in the hospitals of the six districts are then $0, 1, 0, 1, 1, 0$.
• For the fourth patient, since the hospitals in districts $4$ and $5$ are both full, the only option is to use a helicopter to take them off the island.
• Send the fifth patient to the hospital in district $3$. The numbers of patients in the hospitals of the six districts are then $0, 1, 1, 1, 1, 0$.
• For the sixth patient, since the hospitals in districts $2$ and $3$ are both full, the only option is to use a helicopter to take them off the island.
• For the seventh patient, since the hospitals in districts $3$ and $4$ are both full, the only option is to use a helicopter to take them off the island.

In this case, $3$ people are taken off the island by helicopter. It can be proven that this is the maximum.

Sample $1$ satisfies the conditions of subtasks $1 \sim 8$.

Sample $2$ satisfies the conditions of subtasks $2 \sim 8$.

Sample $3$ satisfies the conditions of subtasks $1, 5 \sim 8$.

Samples $4$ and $5$ satisfy the conditions of subtasks $5 \sim 8$.

Constraints

• $2 \le L \le 8\,000$.
• $0 \le C_i \le 8\,000$ ($1 \le i \le L$).
• $1 \le N \le 8\,000$.
• $1 \le X_j \le L − 1$ ($1 \le j \le N$).
• All input numbers are integers.

【Subtasks】

1. ($6$ points) $X_1 \le X_2 \le\cdots\le X_N$.
2. ($7$ points) $L \le 18, N \le 18, C_i = 1$ ($1 \le i \le L$).
3. ($7$ points) $L \le 18, N \le 100, C_i = 1$ ($1 \le i \le L$).
4. ($25$ points) $L \le 100, N \le 100, C_i = 1$ ($1 \le i \le L$).
5. ($25$ points) $L \le 100, N \le 100$.
6. ($10$ points) $L \le 600, N \le 600$.
7. ($15$ points) $L \le 3\,500, N \le 3\,500$.
8. ($5$ points) No additional constraints.

Translated by Starrykiller from the English statement.

Translated by ChatGPT 5