Increasing Array

Problem Statement -

• Time limit: 1.00 s

• Memory limit: 512 MB

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 turn, you may increase the value of any element by one. What is the minimum number of turns 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: the contents of the array.

Output

Print the minimum number of turns.

Constraints

• 1 ≤ n ≤ 2⋅10^5

• 1 ≤ xi ≤ 10^9

Example

Input:

5

3 2 5 1 7

Output:

5

LOGIC

The idea behind this problem is that basically the array should be sorted. But the condition is we are not allowed to move the elements to actually sort the array but increase the value of elements one at at time to sort.

If an element is smaller that the previous one, just find the difference between them. Add this difference to the final answer and update current element to value same as the previous element. Do this for the whole array and we’ll get the number of increments required.

APPROACH

Take an array ‘a’ of size 10^6(Because input can go as high as 2*10^5). Iterate using a for loop, if an element a[i+1] is less than the previous one a[i], take their difference(a[i] - a[i+1]) and add them to the answer. Also update current element a[i+1] to previous element a[i].

CODE

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
 
int main()
{
    ll n, cnt = 0, a[1000007] = {0};
    cin >> n; 
    for(ll i=0; i<n; i++)
    	cin >> a[i];
    for(ll i=0; i<n-1; i++)
    {
        if(a[i+1] < a[i])
        {
            cnt += a[i] - a[i+1];
	    a[i+1] = a[i];
        }
    }
    cout << cnt << endl;
    return 0;
}