#1670. 「USACO 2025.2 Platinum」Min Max Subarrays

注意：本题的时间限制为 3 秒，通常限制的 1.5 倍。

给定一个长为 的整数数组 （，)。输出所有 个 的连续子数组的以下子问题的答案之和。

给定一个非空整数列表，交替执行以下操作（从第一个操作开始）直到列表大小恰好为一。

1. 将列表内的两个相邻整数替换为它们的较小值。
2. 将列表内的两个相邻整数替换为它们的较大值。

求最终余下的整数的最大可能值。

例如，

在第一个数组中， 被替换为 ，随后 被替换为 。

输入的第一行包含 。

第二行包含 。

输出所有连续子数组的子问题的答案之和。

输入 #1

2
2 1

输出 #1

4

输入 #2

3
3 1 3

输出 #2

12

输入 #3

4
2 4 1 3

输出 #3

22

样例 1 解释：

对于 答案为 ，对于 答案为 ，对于 答案为 。

因此，我们的输出应当为 。

样例 3 解释：

考虑子数组 。

1. 在 上应用第一次操作，我们的新数组是 。
2. 在 上应用第二次操作，我们的新数组是 。
3. 在 上应用第三次操作，我们最终的数是 。

可以证明 是最终的数的最大可能值。

• 测试点 ：。
• 测试点 ：。
• 测试点 ：。
• 测试点 ：没有额外限制。