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$. The $i$-th road ($1 \le i \le L-1$) connects districts $i$ and $i+1$ bidirectionally.

The IOI 20XX is planned to be held on JOI Island! However, there is a concern because JOI Island is known as a "furnace" with a high risk of heatstroke, especially for foreigners not accustomed to the hot climate of JOI Island. Therefore, the organizers of IOI have decided to implement the following measures:

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

• During the IOI event, when someone suffers from heatstroke on the $x$-th road ($1 \le x \le L-1$), the heatstroke victim will be taken to a hospital according to the following procedure:

  • The heatstroke victim will be taken to an unfilled hospital in either district $x$ or district $x+1$. If both hospitals are unfilled, it can be taken to either one. If both hospitals are filled, the heatstroke victim will be taken to a hospital outside the island by helicopter.

Since using a helicopter is costly, the organizers want to estimate the maximum number of people who might need to be taken to hospitals outside the island by helicopter. They consider the following scenario:

• Before the IOI event, there are no patients in the hospitals;
• During the IOI event, $N$ people will suffer from heatstroke sequentially. The $j$-th person ($1 \le j \le N$) suffers from heatstroke on the $X_j$-th road;
• For any $1 \le j \le N-1$, when the $(j+1)$-th person suffers from heatstroke, the first $j$ people have already been taken to hospitals. Since the symptoms of heatstroke are severe, no one leaves the hospital during the IOI event.

You need to write a program. Given the number of districts, information about the hospitals, and information about the heatstroke victims, calculate the maximum number of people who might need to be taken to hospitals outside the island by helicopter under the above scenario.

Input Format

The input is formatted as follows:

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

Output Format

Output a single number, which is the maximum number of people who might need to be taken to hospitals outside the island by helicopter.

Sample Input and Output

Input Sample #1

3
1 1 1
3
1 2 2

Output Sample #1

1

Input Sample #2

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

Output Sample #2

3

Input Sample #3

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

Output Sample #3

1

Input Sample #4

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

Output Sample #4

2

Input Sample #5

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

Output Sample #5

3

Notes/Hints

Sample Explanation

For Sample $1$, consider the following scenario:

• The first heatstroke victim is taken to the hospital in district $2$. At this point, the number of patients in the three districts is $0, 1, 0$;
• The second heatstroke victim is taken to the hospital in district $3$. At this point, the number of patients in the three districts is $0, 1, 1$;
• For the third heatstroke victim, since both hospitals in districts $2$ and $3$ are full, they must be taken out of the island by helicopter.

Thus, there is $1$ person taken out of the island by helicopter. It can be proven that this is the maximum.

For Sample $2$, consider the following scenario:

• The first heatstroke victim is taken to the hospital in district $2$. At this point, the number of patients in the six districts is $0, 1, 0, 0, 0, 0$;
• The second heatstroke victim is taken to the hospital in district $4$. At this point, the number of patients in the six districts is $0, 1, 0, 1, 0, 0$;
• The third heatstroke victim is taken to the hospital in district $5$. At this point, the number of patients in the six districts is $0, 1, 0, 1, 1, 0$;
• For the fourth heatstroke victim, since both hospitals in districts $4$ and $5$ are full, they must be taken out of the island by helicopter.
• The fifth heatstroke victim is taken to the hospital in district $3$. At this point, the number of patients in the six districts is $0, 1, 1, 1, 1, 0$;
• For the sixth heatstroke victim, since both hospitals in districts $2$ and $3$ are full, they must be taken out of the island by helicopter.
• For the seventh heatstroke victim, since both hospitals in districts $3$ and $4$ are full, they must be taken out of the island by helicopter.

Thus, there are $3$ people taken out of 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, 5$ satisfy the conditions of Subtasks $5 \sim 8$.

Data Range

• $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.

见题面 Input 部分

见题面 Output 部分