#P12249. [2025年联测]题牌铜

    ID: 11398 传统题 1000ms 512MiB 尝试: 1 已通过: 1 难度: 6 上传者: 标签>贪心数据结构栈排序与序列处理单调栈CF2100数学差分模拟枚举

[2025年联测]题牌铜

题牌铜(eznorb)

题目背景

小 T 曾有一个属于他的序列。风吹过,磨平了序列的峰巅。

题目描述

小 T 有一个长度为 nn 的正整数序列 AA。他可以进行任意多次以下操作:

选择下标 1≤i<j<k≤n1\le i<j<k\le n 满足 i+k=2×ji+k=2\times j,将 AjA_j 修改为 ⌊Ai+Ak2⌋\left\lfloor\dfrac{A_i+A_k}{2}\right\rfloor。

小 T 想要最小化所有操作结束后 ∑i=1nAi\sum_{i=1}^{n}A_i 的值。请你帮他求出这个值。

输入格式

第一行1个一个正整数 nn,表示序列长度。

第二行 nn 个正整数,第 ii 个表示 AiA_i。

输出格式

一行一个正整数,表示操作结束后 ∑i=1nAi\sum_{i=1}^{n}A_i 的最小值。

样例 1

输入

10
4 1 12 1 8 15 16 10 4 3

输出

16

提示

对于所有数据,保证所有数均为正整数,∀i∈[1,n]\forall i\in[1,n],1≤Ai≤10121\le A_i\le10^{12},1≤n≤1061\le n\le10^6。

子任务编号 分值 n≤n\le Ai≤A_i\le 特殊性质
11 1010 100100 200200 无
22 1515 10410^4
33 10610^6 101210^{12} A
44 2020 10410^4 无
55 2×1052\times10^5
66 10610^6

特殊性质 A:保证 ∀i∈[2,n−1]\forall i\in[2,n-1],Ai≥A1A_i\ge A_1 且 Ai≥AnA_i\ge A_n。