U135410 匈奴犯境

本题采用spj，spj代码在最后给出。 中国某西域重镇遭到了匈奴的入侵，该城池有$n$道城门，于是，匈奴单于将军队分为了$n$个部分，每个部分攻打一个城门。匈奴军队单位时间攻城对城池造成的损失等于攻城的人数。 城内的中国将士力量薄弱，只能坚守，不能出战，守城的主帅向朝廷告急。由于该城池关系到丝绸之路的繁荣，皇帝决定派大军救援。但由于军队的集结和动员需要时间，于是命令附近的城池先派遣一队骑兵来协助，帮助城内的守军坚持到援军的到来。 前来协助的骑兵的力量不足以同时对抗匈奴大军，但面对每个城门下的匈奴攻城部队则有绝对的力量优势。并且由于匈奴**轻而不整,贪而无亲,胜不相让,败不相救**。于是当前来协助的骑兵歼灭一股攻城力量的时候，其他的攻城力量不会前来救援，而是继续攻城。 假设你是这队前来救援的骑兵的统帅，请你制定出战斗方案，使得在歼灭匈奴的同时，城池受到的损伤最小。

无

无

如图，中间的图画代表城池，城池外面的折线箭头以及上面的 黑色数字代表坐标系，灰色 的数字代表城门的编号，红色 的点表示攻城的匈奴军队，而 绿色 的点表示救援的骑兵。  **图①**中骑兵正在向$3$号城门奔袭，$3$号城门的距离是$1$，由于骑兵的前进速度为每个单位时间移动单位距离，于是，骑兵到达$3$号城门花费了$1$个单位时间，又因为匈奴军队单位时间攻城对城池造成的损失等于攻城的人数，因此在骑兵到达3号城门的时候，匈奴造成的损失为$(3+4+7+3) \times 1=17$。 然后骑兵赶到了$3$号城门，并歼灭了$3$号城门下的匈奴士兵。如**图②**所示。 然后骑兵前往$0$号城门，$3$号城门到$0$号城门的距离为$|5-4|=1$，于是，骑兵花费了$1$个时间单位，这期间匈奴兵造成的损失为$(3+4+3)*1=10$。 然后骑兵赶到了$0$号城门，并歼灭了$0$号城门下的匈奴士兵。如**图③**所示。 然后骑兵前往$1$号城门，$0$号城门到$1$号城门的距离为$2$，于是，骑兵花费了$2$个时间单位，这期间匈奴兵造成的损失为$(3+4)*2=14$。 然后骑兵赶到了$1$号城门，并歼灭了$1$号城门下的匈奴士兵。如**图④**所示。 然后骑兵前往$2$号城门，$1$号城门到$2$号城门的距离为$2$，于是，骑兵花费了$2$个时间单位，这期间匈奴兵造成的损失为$4*2=8$。 然后骑兵赶到了$2$号城门，并歼灭了$1$号城门下的匈奴士兵。如**图⑤**所示。 至此，所有的匈奴兵被歼灭，造成的损失一共为$17+10+14+8=49$ ## 数据范围 $n \leq 1000$