#NC19838. 可持久化动态图上树状数组维护01背包

可持久化动态图上树状数组维护01背包

题目描述

你有一个长度为 n 序列 {a}(序列下标从1开始) ,每次可以从任意位置 i 花费 ai*i 的代价来把 ai 删除。

注意,删除后 ai 后面的数会依次向前补上(下标 -1 ) 。 求把整个序列删完的最小代价。

输入格式

第一行一个整数 n ,第二行 n 个整数代表该序列。

输出格式

一行一个整数表示删完序列的最小代价。

提示

保证答案在 −263-2^{63} 到 263−12^{63}-1 范围内。

样例 1

2
3 2
5

来源

牛客原题