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 ith 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≤N≤5×105
1≤Arr[i]≤109
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.
