小乖和小坏在玩一个游戏，游戏中有一个长度为 $n$ 的数组$a_1,a_2,...,a_n$ 和一个固定的整数$k$。游戏规则如下，双方都会执行最优策略:

第一步,小乖选择一个非空的区间 $[l, r]$，将这个区间中的所有数字都乘上 $k$。

第二步, 小坏选择一个非空的区间 $[l, r]$, 将这个区间中的所有数字都乘上 $k$。

思路：动态规划

以下思路考场能AC，但是有点问题。

定义$dp[i][j][0]$代表$a[i,...,j]$中连续子段的最小值

定义$dp[i][j][1]$代表$a[i,...,j]$中连续子段的最大值

可以采用二维循环求出dp数组。

之后枚举小乖选择哪个子段，然后计算这个子段情况下小坏所能达到的最小贡献，并取最大值即为最终答案。