题目描述

JOI 岛由 $L$ 个区组成，从西到东依次编号为 $1$ 到 $L$。岛上有 $(L-1)$ 条路，编号为 $1$ 到 $L-1$。第 $i$ 条路（$1\le i\le L-1$）双向连接着区 $i$ 和区 $i+1$。

现在，IOI 20XX 计划在 JOI 岛上举行！然而，令人担心的是，JOI 岛以其“火炉”称号而闻名于世。在岛上中暑风险较高，尤其是对于不适应 JOI 岛炎热气候的外国人。所以，IOI 的组织者决定采取以下措施：

• 对于每一个 $1\le i\le L$，在区 $i$ 上有一个容量为 $C_i$ 人的医院。注意，$C_i$ 可以为 $0$。

• 在 IOI 活动中，当有人在第 $x$ 条路（$1\le x\le L-1$）上中暑时，中暑者将以以下的程序送医：

  • 将中暑者送往区 $x$ 或者区 $x+1$ 上的未满员的医院。如果两个区上的医院都未满员，则送往哪一个医院都可以。如果两个医院都满员了，用直升机将中暑者送往岛外的医院。

由于动用直升机花销不小，组织者们想要估计可能的需要动用直升机的病人数量的最大值。他们考虑如下的情境：

• 在 IOI 活动之前，医院中没有病人；
• 在 IOI 活动中，有 $N$ 个人会依次中暑。第 $j$ 个（$1\le j\le N$）人在第 $X_j$ 条路上中暑；
• 对于任意 $1\le j\le N-1$，当第 $(j+1)$ 个人中暑时，第 $1,2,\cdots,j$ 个人已经送达医院。由于中暑症状较为严重，在 IOI 活动中无人出院。

你需要写一个程序。给定区的数量，医院的信息和中暑者的信息，在上述情境下，计算可能的需要动用直升机的病人数量的最大值。

输入格式

输入格式如下所示：

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

输出格式

输出一行一个数，即可能的需要动用直升机的病人数量的最大值。

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

提示

样例解释

对于样例 $1$，考虑如下的情况：

• 将第一个中暑者送往区 $2$ 上的医院。此时，三个区上的医院的病人数量分别为 $0,1,0$；
• 将第二个中暑者送往区 $3$ 上的医院。此时，三个区上的医院的病人数量分别为 $0,1,1$；
• 对于第三个中暑者，由于区 $2,3$ 上的医院均已满员，所以只能用直升机送出岛。

此时共有 $1$ 人动用直升机送出岛。可以证明这是最大值。

对于样例 $2$，考虑如下的情况：

• 将第一个中暑者送往区 $2$ 上的医院。此时，六个区上的医院的病人数量分别为 $0,1,0,0,0,0$；
• 将第二个中暑者送往区 $4$ 上的医院。此时，六个区上的医院的病人数量分别为 $0,1,0,1,0,0$；
• 将第三个中暑者送往区 $5$ 上的医院。此时，六个区上的医院的病人数量分别为 $0,1,0,1,1,0$；
• 对于第四个中暑者，由于区 $4,5$ 上的医院均已满员，所以只能用直升机送出岛。
• 将第五个中暑者送往区 $3$ 上的医院。此时，六个区上的医院的病人数量分别为 $0,1,1,1,1,0$；
• 对于第六个中暑者，由于区 $2,3$ 上的医院均已满员，所以只能用直升机送出岛。
• 对于第七个中暑者，由于区 $3,4$ 上的医院均已满员，所以只能用直升机送出岛。

此时共有 $3$ 人动用直升机送出岛。可以证明这是最大值。

样例 $1$ 满足子任务 $1\sim 8$ 的条件。

样例 $2$ 满足子任务 $2\sim 8$ 的条件。

样例 $3$ 满足子任务 $1,5\sim 8$ 的条件。

样例 $4,5$ 满足子任务 $5\sim 8$ 的条件。

数据范围

• $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$）；
• 输入数字全为整数。

【子任务】

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）无额外约束。

由 Starrykiller 根据英文题面翻译。