What is the Minimum Number of Deletions to make an array "almost sorted". (Array has unique elements)
The definition of "almost sorted" is given as: By removing one element, the array is strictly increasing (ascending).

This is what I tried.
As it is mentioned the array needs to be strictly increasing apart from one, I found the count of high->low slopes, and returned count-1, as we only need almost sorted.
Also, once an element is deleted at index "i", it doesn't make sense to calculate high->low slope with its neighbor. Instead you have to move forward x number of steps until you find a low->high slope at index "j" for "i" and increase deletionCount by "x" which is equal to "j-i".

But, my approach seems to be flawed somewhere, as the answer is off by 1000s for an array of length 1,00,000.

Also, my initial brute-force O(n^2) solution which is to remove an element and recursively call until the array is almost sorted results in TLE.
This approach needs to be an O(n) or an O(nlogn) solution.

Do you guys know how to solve this, or have seen this question somewhere?