Log in
SOLVE
LATER
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
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 \)
Given Arr[]={1,3,2} . For increasing order sorted data Arr will be {1,2,3}, steps required is 1. For decreasing order sorted data Arr will be {3,2,1}, steps required is 1. So minimum steps are 1.
