Minimum operations

 Problem:-

You are given an array $A$ of length $N$ and can perform the following operation on the array:

• Select a subarray from array $A$ having the same value of elements and decrease the value of all the elements in that subarray by any positive integer $x$.

Find the minimum number of operations required to make all the elements of array $A$ equal to zero.

Input format

• The first line contains an integer $N$ denoting the number of elements in the array.
• The next line contains space-separated integers denoting the elements of array $A$.

Output format

Print the minimum number of operations required to make all the elements of array $A$ equal to zero.

Constraints

$$\begin{gathered} 1\le N\le 5\times {10}^5 \\ 1\le A[i]\le {10}^9 \end{gathered}$$

Sample Input

5
2 2 1 3 1

Sample Output

4

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

• $1^{st}$ Operation , choose subarray [5,5] and x = 1.
  • Array $A$ becomes $[2,2,1,3,0]$
• $2^{nd}$ Operation , choose subarray [3,3] and x = 1.
  • Array $A$ becomes $[2,2,0,3,0]$
• $3^{rd}$ Operation , choose subarray [1,2] and x = 2.
  • Array $A$ becomes $[0,0,0,3,0]$
• $4^{th}$ Operation , choose subarray [4,4] and x = 3.
  • Array $A$ becomes $[0,0,0,0,0]$
• Hence, minimum $4$ operations are required

Code:-

#include<bits/stdc++.h>

using namespace std;

int main()

{

    int n;

    cin>>n;

    long int a[n];

    for(int i=0;i<n;i++)

     cin>>a[i];

    int ans=0;

    for(int i=0;i<n;i++)

    {

        int j=i;

        while(j<n && a[i]==a[j])

        {

            j++;

        }

        i=j-1;

        ans++;

    }

    cout<<ans;

    return 0;

}