You are given an array A with N elements.
You have to sort the array in ascending order. In one move, you can sort the first N-1 elements or the last N-1 elements.
You have to print the minimum number of moves to sort the array. Otherwise output that it is impossible to sort the array.
The first line features a integer N (1 ≤ N ≤ 10^6), denoting the number of elements of array A.
The next line contains N integers Ai (0 ≤ Ai ≤ 10^18) — denoting the array elements.
Print the number of minimum moves to sort the array. Otherwise print "Impossible" without quotes.
Input | Output |
---|---|
5 1 2 3 5 4 | 1 |