All Tracks Algorithms Dynamic Programming Introduction to Dynamic Programming 1 Problem

You are given an array Arr that contains N integers. In one step, you can pick an element from position p and place it before or after some other elements. For example, if you are given an array  \(Arr[]\)={\(1,3,2\)}, then you can pick \(3\) and place it after \(2\). Therefore, the updated array is  \(Arr[]\)={\(1,2,3\)}. 

Your task is to determine the minimum number of steps that is required to sort the data in increasing or decreasing order. 

Input format

• First line: A single integer \(N\) denoting the size of array \(Arr\)
• Second line: \(N\) space-separated integers, where the \(i^{th}\) integer denotes \(Arr[i]\)

Output format

Print a single integer value that denotes the minimum number of steps that is required to sort the data in increasing or decreasing order.

Constraints

\( 1 \le N \le 5 \times 10^5 \)

\( 1 \le Arr[i] \le 10^9 \)