题目描述

在一排左右排列的 $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

说明/提示

数据规模与约定

• 对于 $20\%$ 的数据，$N \le 30$，每个地点的石子数 $\le 30$
• 对于 $40\%$ 的数据，$N \le 300$，每个地点的石子数 $\le 300$
• 对于 $60\%$ 的数据，$N \le 3000$，每个地点的石子数 $\le 3000$
• 对于 $100\%$ 的数据，$1 \le N \le 3000$，每个地点的石子数均大于 $0$ 且不超过 $\le 10^9$