Rainbow 和 Freda 穿过了纵横交错的道路，来到了Poetic Island市旁边的一座山脚下。 这里有排成一行的n座信号塔，其中从左到右第i座的高度为h[i]。Rainbow和Freda将要 在该市盖房子定居了，但是他们认为这n座高低不一的信号塔很是难看。于是他们打算把这 n 座信号塔改造成从左到右高度单调不减的。 Rainbow 和 Freda 可是具有超能力的哦~~~ 他们每次可以选择一座塔，把它合并到两侧 相邻的一座塔上，合并后的高度为两座塔的高度之和。每次合并完成后，被合并的两座塔会 消失；合并成的塔就看做一座新塔，不能再分开。因此每次合并后塔的总数会减少1。他们 想知道，完成他们的目标至少需要多少次合并呢？Rainbow和Freda还是弱爆了有木有！于 是请你帮忙计算一下……

输入共两行：

第一行一个整数n；

第二行n个整数，第i个整数表示h[i]；

输出一个正整数，表示合并需要的次数

8 
1 9 9 4 1 2 2 9

3

对于50%的数据，0< n <=5000；

对于100%的数据，0< n <=10000，0< h[i] <=2147483647，h 均为随机生成。