Almost Sorted

Problem Statement

Almost Sorted Problem Description An array of integers is almost sorted if at most one of its elements can be deleted to leave it perfectly sorted in ascending order. Note the "at most one": an array that is already sorted is almost sorted too. Given an array arr of n distinct integers, report the minimum number of elements that must be deleted so that what remains is almost sorted. For arr = [3, 4, 2, 5, 1] , deleting 2 leaves [3, 4, 5, 1] and deleting 1 leaves [3, 4, 2, 5] ; both are almost sorted, because one further deletion sorts them. One deletion is enough, and none is not, so the answer is 1 . Function Signature Complete the function minDeletions : arr : an unsorted array of n distinct integers. Returns an integer: the minimum number of elements that must be deleted to leave an almost sorted array. Input Format The first line contains the integer n , the array size. The second line contains the n elements of arr . Output Format Print one integer: the minimum number of deletions