Над масивом Василько може здійснювати таку операцію: взяти будь який елемент масиву і зменшити його на одиницю. За яку найменшу кількість операцій масив буде не спадним.

Input

Перший рядок містить натуральне число \(n (1 \le n \le 10^5)\) -- кількість елементів масиву. Другий рядок містить n натуральних чисел, які не перевищують \(10^9\).

Output

Виведіть одне число --- мінімальну кількість операцій, які має виконати Василько, щоб перетворити заданий масив у неспадний.

Sample Input 1

5
3 2 5 4 6

Sample Output 1

2