Given an array arr[] of integers of size n, the task is to check if we can sort the given array in non-decreasing order(i, e.arr[i] ≤ arr[i+1]) by using two types of operation by performing any numbers of time:

• You can choose any index from 1 to n-1(1-based indexing) and increase arr[i] and arr[i+1] by any positive numbers.
• You can choose any index from 1 to n-1 and decrease arr[i] and arr[i+1] by any positive numbers.

Note: Array elements can be negative at any point.

Examples:

Input: arr[] = {6, 4, 3, 5, 2 }
Output: YES
Explanation: 

• Perform type-2 operation on index 1 and choose 4 and Now the array is- {2, 0, 3, 5, 2} 
• Perform type-2 operation on index 3 and choose 4, Now the array becomes {2, 0, -1, 1, 2} 
• Perform type-1 operation on index 2 and choose 2, Now the array becomes {2, 2, 1, 1, 2} 
• Perform type-1 operation on index 3 and choose 1, Now the array becomes {2, 2, 2, 2, 2} 

Now array {2, 2, 2, 2, 2}is sorted.

Input: arr[] = {3, 1, 5, 4 }
Output: NO
Explanation: If we make easily make arr[] = {3, 3, 3, 0} using type-1 operation, Now it is impossible to make the array sorted because we can’t perform an operation on the last index.

Approach: To solve the problem follow the below idea:

• If n is odd, Answer will be always Yes,
  • Let’s prove: We will start from index 2 to n-1 and try to make arr[i] equal to arr[i-1], but we can not perform an operation on the last index. So, After performing the operation, our array will be like this {x, x….., x, y }  y can be equal to x. But if y is not equal to x, we can make all array elements equal by pairing from the initial index and performing an operation on this like this {x, x, x, x, y}. After performing the operation, our array will be like this {x, x ….., x, x } which is sorted.
• If n is even, We will start iterating from index 2 to n-1 and try to make arr[i] equal to arr[i-1] by using increasing or decreasing operations. And in the last, check if 
  arr[n-1] ≤ arr[n], if this condition is satisfied, the Answer will be YES, else NO.

Below are the steps to implement the above idea:

• If n is odd, then print “YES” and return.
• If n is even, then start iterating from index 2 to n-1 and try to make all elements equal to the previous element.
• But we can’t perform an operation on the last index.
• If after iterating from index 2 to n-1, if arr[n-1] ≤ arr[n], so print the answer “YES”, else “NO”.

Below is the implementation of the above approach:

// C++ code for the above approach:

#include <bits/stdc++.h>
using namespace std;

// Function to check can we sort the
// given operation using these two
// types of operation any numbers of time
bool makesorted(int* arr, int n)
{

    // If n is odd,
    if (n % 2 != 0) {
        return true;
    }

    // Iterating from index 1 to n-2
    for (int i = 1; i <= i - 2; i++) {

        // diff = difference between
        // arr[i-1] and arr[i]
        int diff = arr[i - 1] - arr[i];

        // Adding diff to arr[i]
        // and arr[i+1]
        arr[i] += diff;

        // Making all elements equal
        // to first element
        arr[i + 1] += diff;
    }
    if (arr[n - 2] <= arr[n - 1]) {
        return true;
    }
    else {
        return false;
    }
}

// Driver code
int main()
{
    int arr[] = { 3, 1, 5, 4 };
    int n = sizeof(arr) / sizeof(int);

    // Function call
    if (makesorted(arr, n)) {
        cout << "YES" << endl;
    }
    else {
        cout << "NO" << endl;
    }

    return 0;
}

NO

Time Complexity: O(N)
Auxiliary Space: O(1)