Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Sort the Array !

By Dipta_Paul · Limits 1s, 512 MB

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.

Input

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.

Output

Print the number of minimum moves to sort the array. Otherwise print "Impossible" without quotes.

Sample

InputOutput
5
1 2 3 5 4
1

Discussion

Statistics


33% Solution Ratio

Mahim007Earliest, Feb '18

ankonashFastest, 0.1s

sarwarITLightest, 8.1 MB

Shahriar_88Shortest, 991B

Submit

Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.