On the shelf that runs around the perimeter of the library reading room, there are n volumes of works of classic indexed from 1 to n. Volumes are in disarray. The librarian decided to order the volumes, i.e. to place them so that for all i from 1 to n – 1 the volume i will stand side by side with the volume i + 1. There is a lot of volumes, so the librarian would like to minimize the number of his actions. The action is to swap in places any two volumes. It is required to find the minimum number of actions needed to arrange in order all set of volumes.

Input

The first line contains the number n (1 ≤ n ≤ 3000), each of the next n lines contains the volume number in the appropriate place. Each volume number occurs only once.

Output

Print one number - the minimum number of librarian actions.