No testdata at current.

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

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

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

记$sum=\sum\limits_{i=1}^n a_i$ 小团想让$sum$尽可能小，你需要求出最后 $sum$ 的值。