Increasing Array CSES Solution

You are given an array of n integers. You want to modify the array so that it is increasing, i.e., every element is at least as large as the previous element.

On each move, you may increase the value of any element by one. What is the minimum number of moves required?

Input

The first input line contains an integer n: the size of the array.

Then, the second line contains n integers x1,x2,…,xn.x1,x2,…,xn: the contents of the array.

Output

Print the minimum number of moves.

Constraints

• 1≤n≤2⋅1051≤n≤2⋅105
• 1≤xi≤1091≤xi≤109

Example

Input:
5
3 2 5 1 7

Output:
5

Code Solution

//Increasing Array CSES Solution codesagar.in

import java.util.*;
import java.lang.*;
import java.io.*;
 
public class IncArray{
// function to find minimum moves required
// to make the array in increasing order
public static long MinimumMoves(long a[], long n, long x)
{
	// to store answer
	long ans = 0;
 
	// iterate over an array
	for (int i = 1; i < n; i++) {
 
		// non- increasing order
		if (a[i] < a[i - 1]) {
			long p = (a[i - 1] - a[i]) / x;
 
			// add moves to answer
			ans += p;
 
			// increase the element
			a[i] += p * x;
		}
	}
 
	// return required answer
	return ans;
}
 
// Driver code
public static void main(String args[])
{   
        Scanner demo = new Scanner(System.in);
int count=0;
long n=demo.nextLong();
long []arr=new long[(int)n];
while (demo.hasNextLong())
 
 {
 
// Scan an integer value
 
arr[count]=demo.nextLong();
count++;
 
 }
	long x = 1;
	
 
	System.out.println(MinimumMoves(arr, n, x));
 
}
}

//Increasing Array CSES Solution codesgar.in