#Mod13. 胆小菇之梦……这什么玩意儿?

胆小菇之梦……这什么玩意儿?

胆小菇的回忆

昨晚,胆小菇做了个梦,梦见了一行草坪,但是他的前面出现了一堆僵尸!

她十分害怕,但是这时,她发现她前面是一群蘑菇,这个是作者改出来的植物,叫做火炬菇,可以像火炬树桩一样为子弹增伤,但是他是为蘑菇子弹增伤,并且伤害还可以叠加。

具体梦境

这时火炬菇告诉她,她的子弹从第0格开始,初始伤害设为1,每次可以向前快速飞行1-2格,并在到达的格子ii上增伤,但是不同火炬菇的增伤值不等(ai<=100|a_{i}|<=100,不保证ai>0a_{i}>0),她想让她的伤害在n+1n+1格时最大,这样才能打跑僵尸,于是她来向你求救。虽然只是个梦。(谁会拒绝可爱的小菇凉呢)

但是这一切都只是僵尸博士的梦

他梦见胆小菇做了这个梦之后,想要把胆小菇给办掉,所以他来问问你,他该如何让胆小菇的子弹伤害最小,好让他的僵尸大军轻易入侵!

输入格式

第一行输入一个nn,表示草坪长度。

接下来nn个数字,表示不同的火炬菇。

输出格式

一个数,表示她子弹到达第n+1n+1格时的最小值

例样非

5
-1 2 -1 2 3
2

数据范围

保证n<=10000保证n<=10000