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;
}


Recent Posts

See All

Repetitions

Problem Statement - Time limit: 1.00 s Memory limit: 512 MB You are given a DNA sequence: a string consisting of characters A, C, G, and T. Your task is to find the longest repetition in the sequence.

Missing Number

Problem Statement - Time limit: 1.00 s Memory limit: 512 MB You are given all numbers between1,2,…,n except one. Your task is to find the missing number. Input The first input line contains an integer

Weird Algorithm

Problem Statement - Time limit: 1.00 s Memory limit: 512 MB Consider an algorithm that takes as input a positive integer n. If n is even, the algorithm divides it by two, and if n is odd, the algorith

©2019 by EduGeekX. Proudly created with Wix.com