← 返回题目列表

Codeforces · 1667/A

A. 使其增加

中文机器翻译题面 查看原题

给定一个由 $$$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$$$]。