<PREV Problem:
NEXT>
Solved by 181 users: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Permutation complexity

Time limit = 5 seconds

First N integers {1,2,3 ..., N} placed in circle.

Please write a program, witch given an order of numbers in cycle finds minimal number of transpositions of neighbor needed to order them: they should go clockwise 1-> 2-> 3-> ... ->N and after N should go 1. Position of 1 is arbitrary.

Input In the first line N is given. 3 < = N < = 10; In the next line numbers {1, 2, 3 ..., N} are given in clockwise order they placed in circle.

Here goes an example of three step ordering:

--> --> -->

Output One integer number — number of transposition of neighbors needed to order numbers clockwise.

Input#1
5
4 5 1 2 3
Output#1
0
Input#2
3
3 2 1
Output#2
1

Input#3
4
4 3 2 1
Output#3
2

Author:

<PREV | Problem set | Search related messages | NEXT>


© acm.mipt DevGroup
The page was generated in 210ms

SW soft NIX
ID = 54.80.60.91