Make it Increasing

题意翻译

### 题目描述 给定一个包含 $n$ 个**正整数**的数列 $a$ 以及一个长度为 $n$ 的数列 $b$ ,初始时数列 $b$ 的每一个元素都为0。定义一次操作为把数列 $b$ 中的某个元素 $b_i$ 加上或减去 $a_i$ 的值，求使得数列 $b$ 严格递增最小的操作次数。 ### 输入格式 第一行为一个整数 $n$ $(2 \le n \le 5000)$，第二行为 $n$ 个正整数，$a_1$ , $a_2$ , ... , $a_n$ $(1 \le a_i \le {10}^9)$ ，作为数列 $a$ 的值。 ### 输出格式 输出使数列 $b$ 严格递增的最小操作次数。

题目描述

You are given an array $ a $ consisting of $ n $ positive integers, and an array $ b $ , with length $ n $ . Initially $ b_i=0 $ for each $ 1 \leq i \leq n $ . In one move you can choose an integer $ i $ ( $ 1 \leq i \leq n $ ), and add $ a_i $ to $ b_i $ or subtract $ a_i $ from $ b_i $ . What is the minimum number of moves needed to make $ b $ increasing (that is, every element is strictly greater than every element before it)?

输入输出格式

输入格式

The first line contains a single integer $ n $ ( $ 2 \leq n \leq 5000 $ ). The second line contains $ n $ integers, $ a_1 $ , $ a_2 $ , ..., $ a_n $ ( $ 1 \leq a_i \leq 10^9 $ ) — the elements of the array $ a $ .

输出格式

Print a single integer, the minimum number of moves to make $ b $ increasing.

输入输出样例

输入样例 #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

说明

Example $ 1 $ : you can subtract $ a_1 $ from $ b_1 $ , and add $ a_3 $ , $ a_4 $ , and $ a_5 $ to $ b_3 $ , $ b_4 $ , and $ b_5 $ respectively. The final array will be \[ $ -1 $ , $ 0 $ , $ 3 $ , $ 4 $ , $ 5 $ \] after $ 4 $ moves. Example $ 2 $ : you can reach \[ $ -3 $ , $ -2 $ , $ -1 $ , $ 0 $ , $ 1 $ , $ 2 $ , $ 3 $ \] in $ 10 $ moves.