题目描述

商店里面有 $n$ 个苹果，每个苹果都有它的价格。假设第 $i$ 个的价格是 $a_i$。你现在要把他们全部买走。

商店有一个优惠规则：

• 若你 花钱购买 了第 $i$ 个苹果，就能 免费获得 第 $i+1$ 至第 $2\times i$ 个苹果。

你现在需要计算为获得所有苹果的最小花费。

输入格式

第一行为一个整数 $n$，表示苹果的个数。

第二行为 $n$ 个正整数，表示每个苹果的花费。

输出格式

一个数，为获得所有苹果的最小花费。

8
26 18 6 12 49 7 45 45

39

数据范围

$1\le n\le 2000, 1\le a_i\le 10^6$