CF1687A The Enchanted Forest

> 其实这里被称为魔法森林，基本上就是因为这些有幻觉效果的蘑菇。光是接近这些蘑菇，就好像被施了魔法而产生幻觉。——《东方求闻史纪》 魔理沙来到了魔法森林采摘蘑菇。 魔法森林可以被抽象成一条有着 $n$ 个节点，从 $1$ 到 $n$ 标号的数轴。在魔理沙出发之前，她的好友帕秋莉运用魔法去侦测了每个节点上的蘑菇数量，分别为 $a_1,a_2,\dots,a_n$。 在第 $0$ 分钟的时候，魔理沙可以从任意一个节点出发。在每一分钟的时候，她将会做以下事情： - 她将从节点 $x$ 移动到节点 $y$（$|x-y| \leq 1$，即 $y$ 可能等于 $x$） - 她将会收集节点 $y$ 上的所有蘑菇。 - 魔法森林中每个节点会再生长出一个蘑菇。 注意，她不能在第 $0$ 分钟的时候收集蘑菇。 现在魔理沙希望知道她在前 $k$ 分钟的时候，最多能收集到多少个蘑菇。请你帮帮她。

无

无

Test case 1: Marisa can start at $ x=2 $ . In the first minute, she moves to $ x=1 $ and collect $ 5 $ mushrooms. The number of mushrooms will be $ [1,7,2,3,4] $ . In the second minute, she moves to $ x=2 $ and collects $ 7 $ mushrooms. The numbers of mushrooms will be $ [2,1,3,4,5] $ . After $ 2 $ minutes, Marisa collects $ 12 $ mushrooms. It can be shown that it is impossible to collect more than $ 12 $ mushrooms. Test case 2: This is one of her possible moving path: $ 2 \rightarrow 3 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5 $ It can be shown that it is impossible to collect more than $ 37 $ mushrooms.