题目背景

试题来源：https://koi.or.kr/archives/。中文翻译做了少量本土化修改。

按照署名—非商业性使用—相同方式共享 4.0 协议国际版进行授权。

题目描述

在一排左右排列的 $N$ 个地点中，每个地点上都放有若干个鹅卵石。

哲洙可以进行的操作有以下两种：

1. 从相邻的两个地点中，拿走任意相同数量的鹅卵石；
2. 从一个地点中，拿走任意数量的鹅卵石。

即使某个地点上的鹅卵石被拿完，该地点依旧保留，两个原本不相邻的地点不会因此变得相邻。

哲洙会不断重复执行上述两种操作中的一种，直到将所有鹅卵石都拿走。

给定每个地点初始时的鹅卵石数量，请编写一个程序，计算哲洙最少需要多少次操作，才能拿走所有鹅卵石。

输入格式

第一行给出地点数量 $N$。

第二行给出 $N$ 个整数，表示每个地点的初始鹅卵石数量，按从左至右的顺序，以空格分隔。

输出格式

输出一行，表示拿走所有鹅卵石所需的最少操作次数。

2
1 2

2

4
1 1 3 3

2

3
1 4 3

2

5
2 3 6 10 5

4

提示

约束条件

• $2 \leq N \leq 2500$
• 每个地点初始的鹅卵石数量为不小于 1 且不超过 $10^8$ 的整数

子任务

1. （6 分）$N = 3$
2. （11 分）$N \leq 15$
3. （19 分）$N \leq 300$
4. （27 分）每个地点的初始鹅卵石数量不超过 2500
5. （37 分）无额外约束条件

翻译由 ChatGPT-4o 完成