English · Original
Chinese · Translation
Formal · Original
Polycarp plans to conduct a load testing of its new project Fakebook. He already agreed with his friends that at certain points in time they will send requests to Fakebook. The load testing will last _n_ minutes and in the _i_\-th minute friends will send _a__i_ requests.
Polycarp plans to test Fakebook under a special kind of load. In case the information about Fakebook gets into the mass media, Polycarp hopes for a monotone increase of the load, followed by a monotone decrease of the interest to the service. Polycarp wants to test this form of load.
Your task is to determine how many requests Polycarp must add so that before some moment the load on the server strictly increases and after that moment strictly decreases. Both the increasing part and the decreasing part can be empty (i. e. absent). The decrease should immediately follow the increase. In particular, the load with two equal neigbouring values is unacceptable.
For example, if the load is described with one of the arrays _\[1, 2, 8, 4, 3\]_, _\[1, 3, 5\]_ or _\[10\]_, then such load satisfies Polycarp (in each of the cases there is an increasing part, immediately followed with a decreasing part). If the load is described with one of the arrays _\[1, 2, 2, 1\]_, _\[2, 1, 2\]_ or _\[10, 10\]_, then such load does not satisfy Polycarp.
Help Polycarp to make the minimum number of additional requests, so that the resulting load satisfies Polycarp. He can make any number of additional requests at any minute from 1 to _n_.
## Input
The first line contains a single integer _n_ (1 ≤ _n_ ≤ 100 000) — the duration of the load testing.
The second line contains _n_ integers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 109), where _a__i_ is the number of requests from friends in the _i_\-th minute of the load testing.
## Output
Print the minimum number of additional requests from Polycarp that would make the load strictly increasing in the beginning and then strictly decreasing afterwards.
[samples]
## Note
In the first example Polycarp must make two additional requests in the third minute and four additional requests in the fourth minute. So the resulting load will look like: _\[1, 4, 5, 6, 5\]_. In total, Polycarp will make 6 additional requests.
In the second example it is enough to make one additional request in the third minute, so the answer is 1.
In the third example the load already satisfies all conditions described in the statement, so the answer is 0.
Polycarp 计划对其新项目 Fakebook 进行负载测试。他已与朋友们约定，在特定时间点向 Fakebook 发送请求。负载测试将持续 #cf_span[n] 分钟，在第 #cf_span[i] 分钟，朋友们将发送 #cf_span[ai] 个请求。
Polycarp 计划以一种特殊类型的负载测试 Fakebook。如果有关 Fakebook 的信息进入大众媒体，Polycarp 希望负载呈现单调递增，随后单调递减。Polycarp 希望测试这种形式的负载。
你的任务是确定 Polycarp 必须增加多少个请求，使得在某一时刻之前，服务器负载严格递增，之后严格递减。递增部分和递减部分均可为空（即不存在）。递减部分必须紧接在递增部分之后。特别地，两个相邻值相等的负载是不允许的。
例如，如果负载由数组 _[1, 2, 8, 4, 3]_、_[1, 3, 5]_ 或 _[10]_ 描述，则该负载满足 Polycarp 的要求（每种情况中，均存在一个递增部分，紧接着是递减部分）。如果负载由数组 _[1, 2, 2, 1]_、_[2, 1, 2]_ 或 _[10, 10]_ 描述，则该负载不满足 Polycarp 的要求。
帮助 Polycarp 以最少的额外请求次数，使最终负载满足上述条件。他可以在第 #cf_span[1] 到第 #cf_span[n] 分钟中的任意分钟增加任意数量的请求。
第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 100 000]) —— 负载测试的持续时间。
第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an] (#cf_span[1 ≤ ai ≤ 109])，其中 #cf_span[ai] 表示第 #cf_span[i] 分钟朋友们发送的请求数量。
输出 Polycarp 需要增加的最少额外请求数量，使得负载在开始时严格递增，随后严格递减。
## Input
第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 100 000]) —— 负载测试的持续时间。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an] (#cf_span[1 ≤ ai ≤ 109])，其中 #cf_span[ai] 表示第 #cf_span[i] 分钟朋友们发送的请求数量。
## Output
输出 Polycarp 需要增加的最少额外请求数量，使得负载在开始时严格递增，随后严格递减。
[samples]
## Note
在第一个例子中，Polycarp 必须在第三分钟增加两个请求，在第四分钟增加四个请求。因此最终负载为：_[1, 4, 5, 6, 5]_。Polycarp 总共增加了 #cf_span[6] 个请求。
在第二个例子中，只需在第三分钟增加一个请求即可，因此答案是 #cf_span[1]。
在第三个例子中，负载已满足题目描述的所有条件，因此答案是 #cf_span[0]。
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the duration of load testing.
Let $ A = (a_1, a_2, \dots, a_n) $ be the sequence of requests per minute, where $ a_i \in \mathbb{Z}^+ $.
**Objective**
Find the minimum total number of additional requests to transform $ A $ into a sequence $ B = (b_1, b_2, \dots, b_n) $ such that:
- There exists an index $ k \in \{1, 2, \dots, n\} $ where:
- $ b_1 < b_2 < \dots < b_k $ (strictly increasing),
- $ b_k > b_{k+1} > \dots > b_n $ (strictly decreasing).
- $ b_i \geq a_i $ for all $ i \in \{1, \dots, n\} $,
- The total increase $ \sum_{i=1}^n (b_i - a_i) $ is minimized.
**Constraints**
1. $ 1 \leq n \leq 100{,}000 $
2. $ 1 \leq a_i \leq 10^9 $ for all $ i $
3. $ b_i \in \mathbb{Z}^+ $ for all $ i $
API Response (JSON)
{
"problem": {
"name": "H. Load Testing",
"description": {
"content": "Polycarp plans to conduct a load testing of its new project Fakebook. He already agreed with his friends that at certain points in time they will send requests to Fakebook. The load testing will last ",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 1000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF847H"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Polycarp plans to conduct a load testing of its new project Fakebook. He already agreed with his friends that at certain points in time they will send requests to Fakebook. The load testing will last ...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Polycarp 计划对其新项目 Fakebook 进行负载测试。他已与朋友们约定，在特定时间点向 Fakebook 发送请求。负载测试将持续 #cf_span[n] 分钟，在第 #cf_span[i] 分钟，朋友们将发送 #cf_span[ai] 个请求。\n\nPolycarp 计划以一种特殊类型的负载测试 Fakebook。如果有关 Fakebook 的信息进入大众媒体，Polycarp 希望负...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z}^+ $ be the duration of load testing. \nLet $ A = (a_1, a_2, \\dots, a_n) $ be the sequence of requests per minute, where $ a_i \\in \\mathbb{Z}^+ $. \n\n**Objectiv...",
"is_translate": false,
"language": "Formal"
}
]
}