题牌铜(eznorb)
题目背景
小 T 曾有一个属于他的序列。风吹过,磨平了序列的峰巅。
题目描述
小 T 有一个长度为 n 的正整数序列 A。他可以进行任意多次以下操作:
选择下标 1≤i<j<k≤n 满足 i+k=2×j,将 Aj 修改为 ⌊2Ai+Ak⌋。
小 T 想要最小化所有操作结束后 ∑i=1nAi 的值。请你帮他求出这个值。
输入格式
第一行1个一个正整数 n,表示序列长度。
第二行 n 个正整数,第 i 个表示 Ai。
输出格式
一行一个正整数,表示操作结束后 ∑i=1nAi 的最小值。
样例 1
输入
10
4 1 12 1 8 15 16 10 4 3
输出
16
提示
对于所有数据,保证所有数均为正整数,∀i∈[1,n],1≤Ai≤1012,1≤n≤106。
| 子任务编号 |
分值 |
n≤ |
Ai≤ |
特殊性质 |
| 1 |
10 |
100 |
200 |
无 |
| 2 |
15 |
104 |
| 3 |
106 |
1012 |
A |
| 4 |
20 |
104 |
无 |
| 5 |
2×105 |
| 6 |
106 |
特殊性质 A:保证 ∀i∈[2,n−1],Ai≥A1 且 Ai≥An。