#P1345. [Baltic2007]序列问题Sequence

[Baltic2007]序列问题Sequence

题目描述

对于一个给定的序列 a1, a2, ⋯ , ana_1,\ a_2,\ \cdots,\ a_n,我们对它进行一个操作 reduce(i)\text{reduce}(i),该操作将数列中的元素 aia_i 和 ai+1a_{i+1} 用一个元素 max⁡(ai, ai+1)\max(a_i,\ a_{i+1}) 替代,这样得到一个比原来序列短的新序列。这一操作的代价是 max⁡(ai, ai+1)\max(a_i,\ a_{i+1})。进行 n−1n-1 次该操作后,可以得到一个长度为 11 的序列。

我们的任务是计算代价最小的 reduce\text{reduce} 操作步骤,将给定的序列变成长度为 11 的序列。

输入格式

第一行为一个整数 nn(1≤n≤1061\leq n\leq 10^6),表示给定序列的长度。

接下来的 nn 行,每行一个整数 aia_i(0≤ai≤1090\leq a_i\leq 10^9),为序列中的元素。

输出格式

只有一行,为一个整数,即将序列变成一个元素的最小代价。

3
1
2
3
5

数据范围

对于 30%30\% 的测试数据,n≤500n\le 500;

对于 50%50\% 的测试数据,n≤20000n \le 20000;

对于 100%100\% 的测试数据,1≤n≤1061 \le n \le 10^6,0≤ai≤1090 \le a_i \le 10^9。