Polycarp 计划对其新项目 Fakebook 进行负载测试。他已经与朋友们达成一致,在某些时间点他们会向 Fakebook 发送请求。负载测试将持续n分钟,在第i分钟朋友将发送ai请求。
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 ≤ n ≤ 100 000) — 负载测试的持续时间。
第二行包含n个整数a1, a2, ..., an (1 ≤ ai ≤ 109),其中ai是负载测试第i分钟内来自好友的请求数。
输出
打印来自 Polycarp 的额外请求的最小数量,该请求将使负载在开始时严格增加,然后严格减少。
示例
输入 #1
5 1 4 3 2 5
输出 #1
6
输入 #2
5 1 2 2 2 1
输出 #2
1
输入 #3
7 10 20 40 50 70 90 30
输出 #3
0
注意
在第一个示例中,Polycarp 必须在第三分钟内提出两个附加请求,并在第四分钟内提出四个附加请求。因此生成的负载将如下所示:[1,4,5,6,5]。波利卡普总共将提出 6 项额外请求。
在第二个示例中,在第三分钟内发出一个附加请求就足够了,因此答案为 1。
在第三个示例中,负载已经满足语句中描述的所有条件,因此答案为 0。