CF847H Load Testing

Polycarp 计划对他的新项目 Fakebook 进行负载测试。他已经与朋友们约定，在特定时间点向 Fakebook 发送请求。负载测试将持续 $n$ 分钟，第 $i$ 分钟他的朋友们将发送 $a_i$ 个请求。 Polycarp 计划在一种特殊的负载下测试 Fakebook。如果 Fakebook 的消息传到了大众媒体，Polycarp 希望负载表现为先单调递增，然后紧接着单调递减。他想测试服务器在这种负载下的表现。 你的任务是确定 Polycarp 至少需要增加多少个请求，使得在某一时刻之前（包括该时刻）服务器的负载严格递增，在那之后严格递减。递增部分和递减部分都可以为空（即不存在递增或递减部分也是允许的）。递减部分应紧接着递增部分。特别地，不能有两个相等的相邻数值。 例如，若负载可描述为以下数组之一 \[1, 2, 8, 4, 3\]，\[1, 3, 5\] 或 \[10\]，则负载满足 Polycarp 的要求（每种情况都是严格递增后紧接着严格递减）。而以下任一数组 \[1, 2, 2, 1\]，\[2, 1, 2\] 或 \[10, 10\]，则不满足 Polycarp 的要求。 请帮助 Polycarp 计算最少需要增加多少个请求，使得最终的负载满足 Polycarp 的要求。他可以在 $1$ 到 $n$ 分钟中的任意时刻增加任意数量的请求。

第一行包含一个整数 $n$（$1 \leq n \leq 100000$），表示负载测试的时长。 第二行包含 $n$ 个整数 $a_1, a_2, ..., a_n$（$1 \leq a_i \leq 10^9$），其中 $a_i$ 表示第 $i$ 分钟朋友们发送的请求数。

输出使得负载曲线先严格递增后严格递减所需的最小新增请求数。

在第一个示例中，Polycarp 必须在第三分钟增加两个请求，在第四分钟增加四个请求。最终的负载为 \[1, 4, 5, 6, 5\]。因此，Polycarp 总共增加了 $6$ 个请求。 在第二个示例中，只需在第三分钟增加 1 个请求，即可得到答案 $1$。 在第三个示例中，负载已经完全满足题意条件，因此答案为 $0$。 由 ChatGPT 5 翻译