给定一个由 $$$n$$$ 正整数组成的数组 $$$a$$$ 和一个长度为 $$$n$$$ 的数组 $$$b$$$。最初,对于每个 $$$1 \leq i \leq n$$$,$$$b_i=0$$$。
在一步操作中,您可以选择一个整数 $$$i$$$ ($$$1 \leq i \leq n$$$),并将 $$$a_i$$$ 添加到 $$$b_i$$$ 或从 $$$b_i$$$ 中减去 $$$a_i$$$。使 $$$b$$$ 增加(即每个元素都严格大于它之前的每个元素)所需的最小移动次数是多少?
输入
第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 5000$$$)。
第二行包含 $$$n$$$ 整数、$$$a_1$$$、$$$a_2$$$、...、$$$a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — 数组 $$$a$$$ 的元素。
输出
打印一个整数,使 $$$b$$$ 增加的最小移动次数。
示例
输入 #1
5 1 2 3 4 5
输出 #1
4
输入 #2
7 1 2 1 2 1 2 1
输出 #2
10
输入 #3
8 1 8 2 7 3 6 4 5
输出 #3
16
注意
示例$$$1$$$:您可以从$$$b_1$$$中减去$$$a_1$$$,然后将$$$a_3$$$、$$$a_4$$$和$$$a_5$$$分别添加到$$$b_3$$$、$$$b_4$$$和$$$b_5$$$。 $$$4$$$ 移动后,最终数组将是 [$$$-1$$$, $$$0$$$, $$$3$$$, $$$4$$$, $$$5$$$]。
示例 $$$2$$$:您可以在 $$$10$$$ 移动中到达 [$$$-3$$$, $$$-2$$$, $$$-1$$$, $$$0$$$, $$$1$$$, $$$2$$$, $$$3$$$]。