06768. USACO·最小最大子数组 未做

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

给定一个长为 $N$ 的整数数组 $a_1,a_2,\dots ,a_N$（$2\le N\le 10^6$，$1\le a_i\le N$)。输出所有 $N(N+1)/2$ 个 $a$ 的连续子数组的以下子问题的答案之和。

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

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

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

例如，

[4, 10, 3] -> [4, 3] -> [4]

[3, 4, 10] -> [3, 10] -> [10]

在第一个数组中，$(10,3)$ 被替换为 $\min (10,3)=3$，随后 $(4,3)$ 被替换为 $\max (4,3)=4$。

输入的第一行包含 $N$。

第二行包含 $a_1,a_2,\dots ,a_N$。

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

【样例解释】

考虑子数组 $[2,4,1,3]$。

• 在 (1, 3) 上应用第一次操作，我们的新数组是 $[2,4,1]$。

• 在 (4, 1) 上应用第二次操作，我们的新数组是 $[2,4]$。

• 在 (2, 4) 上应用第三次操作，我们最终的数是 $2$。

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

• 测试点 6-7：$N\le 5000$。

• 测试点 8-9：$\max (a)\le 10$。

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

【数据规模与约定】

• 测试点 4-5：$N\le 100$。

• 测试点 6-7：$N\le 5000$。

• 测试点 8-9：$\max (a)\le 10$。

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

供题：Benjamin Qi