题目描述
对于一个给定的序列 a1, a2, ⋯, an,我们对它进行一个操作 reduce(i),该操作将数列中的元素 ai 和 ai+1 用一个元素 max(ai, ai+1) 替代,这样得到一个比原来序列短的新序列。这一操作的代价是 max(ai, ai+1)。进行 n−1 次该操作后,可以得到一个长度为 1 的序列。
我们的任务是计算代价最小的 reduce 操作步骤,将给定的序列变成长度为 1 的序列。
输入格式
第一行为一个整数 n(1≤n≤106),表示给定序列的长度。
接下来的 n 行,每行一个整数 ai(0≤ai≤109),为序列中的元素。
输出格式
只有一行,为一个整数,即将序列变成一个元素的最小代价。
3
1
2
3
5
数据范围
对于 30% 的测试数据,n≤500;
对于 50% 的测试数据,n≤20000;
对于 100% 的测试数据,1≤n≤106,0≤ai≤109。