背景

在美丽富饶的Katharon国中生活着一群快乐的小木偶。他们衣食无忧,自给自足。然而在某一天,来自外星的X国要对Katharon国发起攻击,国家安危迫在眉睫,下面请你来做战前的防御准备工作。

描述

我们定义战线为一条长度为的序列,在这条战线上共设有个检查点,从左到右依次标号为。一个战线为合法战线当且仅当任意一个检查点可以通过安全检查。对于第个检查点可以通过安全检查的方式有两种,第一种是放置一个守卫塔,这将花费的费用。第二种方式是放置一个木偶,放置木偶的花费等于这个检查点右侧的第一个守卫塔到它的距离。举例来说,若检查点放置一个木偶,检查点右侧的第一个守卫塔位置为),则在点放置木偶的花费为。当然,第个检查点只能放置守卫塔,因为它的右面不可能再存在别的守卫塔了。我们定义战线花费为所有守卫塔的花费加上所有木偶的花费,现在Katharon国的国王hzc君将提供给你每个位置放置守卫塔的费用以及战线的总长度,请你求出最小的战线花费值。

输入格式

第一行为一个整数表示战线的总长度。

第二行个整数,第个整数表示在位置放置守卫塔的花费

输出格式

共一个整数,表示最小的战线花费值。

样例输入

10
2 3 1 5 4 5 6 3 1 2

样例输出

18

数据范围与约定

对于全部测试数据满足:

样例解释

位置

1

2

3

4

5

6

7

8

9

10

总计

防御方式

守卫塔

木偶

守卫塔

木偶

守卫塔

木偶

木偶

木偶

守卫塔

守卫塔

 

守卫塔花费

2

 

1

 

4

 

 

 

1

2

10

木偶花费

 

1

 

1

 

3

2

1

 

 

8

总计

2

1

1

1

4

3

2

1

1

2

18