背景

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

描述

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

输入格式

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

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

输出格式

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

样例输入

10
2 3 1 5 4 5 6 3 1 2

样例输出

18

数据范围与约定

对于全部测试数据满足：，。

样例解释