CF847H.Load Testing

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.

Polycarp 计划对其新项目 Fakebook 进行负载测试。他已与朋友们约定，在某些特定时刻向 Fakebook 发送请求。负载测试将持续 $ n $ 分钟，且在第 $ i $ 分钟，朋友们将发送 $ a_i $ 个请求。

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 计算所需的最少额外请求总数，使得最终负载满足上述要求。他可以在第 $ 1 $ 分钟至第 $ n $ 分钟中的任意一分钟添加任意数量的额外请求。

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.

第一行包含一个整数 $n$（$1 \leq n \leq 100\,000$）—— 表示负载测试的持续时间（单位：分钟）。

第二行包含 $n$ 个整数 $a_1,\,a_2,\,\ldots,\,a_n$（$1 \leq a_i \leq 10^9$），其中 $a_i$ 表示负载测试第 $i$ 分钟内来自朋友的请求数量。

Print the minimum number of additional requests from Polycarp that would make the load strictly increasing in the beginning and then strictly decreasing afterwards.

输出Polycarp需要额外发出的最少请求数，使得负载序列在前半段严格递增，后半段严格递减。

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 必须在第三分钟额外发出两次请求，在第四分钟额外发出四次请求。因此，最终的负载序列为：[1, 4, 5, 6, 5]。总计，Polycarp 将额外发出 6 次请求。

在第二个例子中，仅需在第三分钟额外发出一次请求即可，因此答案为 1。

在第三个例子中，当前负载已满足题目描述的所有条件，因此答案为 0。