题目描述

译自 JOI Open 2024 T2 「熱中症 / Heat Stroke」

JOI 岛是由东西一列排列的 $L$ 个地区组成，每个地区从西边开始按顺序编号为 $1$ 到 $L$。另外，JOI 岛上有 $L-1$ 条道路，具体来说，对于每个 $1 \leq i \leq L-1$，地区 $i$ 和地区 $i+1$ 之间有一条双向的道路。这里，地区 $i$ 和地区 $i+1$ 之间的道路被称为道路 $i$。

20XX 年，IOI 在 JOI 岛上举行。JOI 岛是一个闻名的酷暑之地，对于不习惯炎热的海外选手来说，中暑的风险很高。因此，IOI 的组织者制定了以下的对策。

• 在每个地区 $i\ (1 \leq i \leq L)$，准备一个可以容纳 $C_{i}$ 人的医院。但是可能存在 $C_{i}=0$ 的情况。
• 在 IOI 的举办期间，如果在道路 $x\ (1 \leq x \leq L-1)$ 上发生了中暑患者，就按照以下的步骤把患者送往医院住院。
  • 把患者用救护车送往地区 $x$ 和地区 $x+1$ 的医院中可以住院的一方住院。如果两边都可以住院，那么有可能被送往任意一边。如果两边的医院都不能住院，那么就用直升机送往岛外的综合医院住院。

但是，用直升机送往医院的费用很高，所以组织者想知道最多有多少人会被直升机送往医院。他们以以下场景为例：

• 在 IOI 开始的时候，所有的医院都没有住院患者。
• 在 IOI 的举办期间，总共出现了 $N$ 个的中暑患者。第 $j\ (1 \leq j \leq N)$ 个的患者是在道路 $X_{j}$ 上中暑的。
• 对于每个 $1 \leq j \leq N-1$，在第 $j+1$ 个患者中暑的时候，第 $j$ 个以前的患者已经住院了。另外，中暑患者都是重症，所以在举办期间不会出院。

给定地区的数量，医院和中暑患者的信息，请实现一个程序求出在上述场景中，最多有多少人会被直升机送往医院。

输入格式

第一行包含一个整数 $L$。

第二行包含 $L$ 个整数 $C_1, C_2, \ldots , C_L$。

第三行包含一个整数 $N$。

第四行包含 $N$ 个整数 $X_1, X_2, \ldots , X_N$。

输出格式

输出一个整数，表示最多有多少人会被直升机送往医院。

3
1 1 1
3
1 2 2

1

以下的情况，有 $1$ 个患者会被直升机送往医院。

1. 第 $1$ 个患者被送往地区 $2$ 的医院住院。地区 $1,2,3$ 的医院的住院人数变成 $0,1,0$ 人。
2. 第 $2$ 个患者被送往地区 $3$ 的医院住院。地区 $1,2,3$ 的医院的住院人数变成 $0,1,1$ 人。
3. 第 $3$ 个患者，因为地区 $2$ 和地区 $3$ 的两边的医院都已经不能住院了，所以被直升机送往岛外医院住院。

没有 $2$ 个以上的患者会被直升机送往医院的情况，所以输出 $1$。

这组样例满足子任务 $1,2,3,4,5,6,7,8$ 的限制。

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

3

以下的情况，有 3 个患者会被直升机送往医院。

1. 第 $1$ 个患者被送往地区 $2$ 的医院住院。地区 $1,2,3,4,5,6$ 的医院的住院人数变成 $0,1,0,0,0,0$ 人。
2. 第 $2$ 个患者被送往地区 $4$ 的医院住院。地区 $1,2,3,4,5,6$ 的医院的住院人数变成 $0,1,0,1,0,0$ 人。
3. 第 $3$ 个患者被送往地区 $5$ 的医院住院。地区 $1,2,3,4,5,6$ 的医院的住院人数变成 $0,1,0,1,1,0$ 人。
4. 第 $4$ 个患者，因为地区 $4$ 和地区 $5$ 的两边的医院都已经不能住院了，所以被直升机送往岛外医院住院。
5. 第 $5$ 个患者被送往地区 $3$ 的医院住院。地区 $1,2,3,4,5,6$ 的医院的住院人数变成 $0,1,1,1,1,0$ 人。
6. 第 $6$ 个患者，因为地区 $2$ 和地区 $3$ 的两边的医院都已经不能住院了，所以被直升机送往岛外医院住院。
7. 第 $7$ 个患者，因为地区 $3$ 和地区 $4$ 的两边的医院都已经不能住院了，所以被直升机送往岛外医院住院。

不存在医疗直升机运送四名或四名以上患者的情况，因此输出 $3$。

这组样例满足子任务 $2,3,4,5,6,7,8$ 的限制。

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

1

这组样例满足子任务 $1,5,6,7,8$ 的限制。

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

2

这组样例满足子任务 $5,6,7,8$ 的限制。

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

这组样例满足子任务 $5,6,7,8$ 的限制。

数据范围与提示

对于所有输入数据，满足：

• $2 \leq L \leq 8000$
• $0 \leq C_{i} \leq 8000\ (1 \leq i \leq L)$
• $1 \leq N \leq 8000$
• $1 \leq X_{j} \leq L-1\ (1 \leq j \leq N)$

详细子任务附加限制及分值如下表所示。