你是一个医疗队的负责人，任务是使用一种新的实验性药物治疗非洲某国几个村庄的埃博拉病毒。该国唯一的公路旁分布着 $n$ 个村庄，沿公路从 $1$ 到 $n$ 编号。在第一天的早晨，你位于 1 号村庄。

起初，第 $i$ 个村庄有 $a_i$ 人感染了埃博拉病毒。每天你可以执行以下操作之一：

• 要么治愈你当前所在村庄的所有感染者；
• 要么移动到相邻的村庄。

如果在一天结束时，某个村庄仍有 $k$ 个感染者，他们会感染该村庄的另外 $k$ 个人，然后死去。因此，实际上在每个未治愈的村庄中，感染人数保持不变，但每天都会有 $a_i$ 个新的人死去。

你希望治愈所有村庄的人，使得最终死亡的总人数尽可能少。

然而，有一个限制：人们不能失去希望。因此，有时你的行动会受到以下规则的约束。假设你进入了第 $i$ 个村庄，并决定不治愈其中的人，而是在第二天前往另一个村庄。在这种情况下，如果之后你决定从村庄 $j$ 移动到村庄 $j'$，且 $j'$ 比 $j$ 更接近 $i$，那么你必须继续朝这个方向移动，直到到达村庄 $i$，并且在到达时必须治愈村庄 $i$ 中的人。不过，在此过程中，你可以停下来治愈途中经过的中间村庄。

例如，假设你最初在村庄 1。第一天你移动到村庄 2。第二天你移动到村庄 3。第三天你治愈村庄 3 的人。第四天你移动到村庄 2。现在，根据上述规则，你被迫去治愈村庄 2 的人。同时，在到达并治愈村庄 1 之前，你不允许移动到编号更大的村庄。因此，你必须在第 5 天治愈村庄 2 的人，在第 6 天移动到村庄 1，并在第 7 天治愈那里的人。现在你又可以自由选择你的行动了。

输入格式

输入文件包含多组测试数据。

每个测试数据的第一行包含一个整数 $n$ —— 村庄的数量（$1 \le n \le 3000$）。

下一行包含 $n$ 个整数：$a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$）。

输入以一行 $n = 0$ 结束。

一个文件中所有测试数据的 $n$ 之和不超过 3000。

输出格式

对于每组测试数据，输出一个整数：在所有村庄的人都被治愈之前，可能死亡的最少人数。

样例

输入样例 1

6
40 200 1 300 2 10
0

输出样例 1

1950

说明

在给定的样例中，最优的行动顺序如下：前往村庄 2，治愈村庄 2 的人，前往村庄 3，前往村庄 4，治愈村庄 4 的人，前往村庄 3，治愈村庄 3 的人（被迫），前往村庄 2（被迫），前往村庄 1（被迫），治愈村庄 1 的人（被迫），前往村庄 2, 3, 4, 5, 6，治愈村庄 6 的人，前往村庄 5，治愈村庄 5 的人（被迫，尽管无论如何都需要这样做）。

整个治疗过程共耗时 18 天，每天死亡的人数分别为：553, 353, 353, 353, 53, 53, 52, 52, 52, 12, 12, 12, 12, 12, 12, 2, 2, 0。