OJ现已增加邮箱找回密码功能,还没有绑定邮箱的同学们请抓紧时间,以免密码丢失无法找回


问题 F: 古法排序

问题 F: 古法排序

时间限制: 1 Sec  内存限制: 128 MB
提交: 233  解决: 49
[提交] [状态] [讨论版] [命题人:]

题目描述

“姓名?”
“槐诗。”
“性别?”
“男。”
“年龄?”
“十七。”
如露头角的命定之人槐诗终于进入象牙之塔得到谱系之主罗素的接见。慈爱的罗素给初次见面的槐诗出了一道题目,考察槐诗的思维能力。

题目如下:
给定含n个整数的数组a。每次操作可以选择数组中任意一个元素使其增加1。你可以进行任意次操作(也可以不进行操作),请问至少需要多少次操作使得数组a变成严格递增的数组。

你能帮帮槐诗解决这道题目,成功进入象牙之塔么?

注:如果长度为n的数组a满足a1<a2<a3<...<an,则称此数组为严格递增的数组。

输入

第一行输入一个正整数n,代表数组长度。
第二行输入n个数ai,代表数组的每一个元素。
2<=n<=2e5,-1e9<=ai<=1e9.

输出

输出一个整数,代表所需要的最少代价。

样例输入 Copy

7
1 3 2 4 8 5 7

样例输出 Copy

10