Circular Table Guest Arrangement

There are n guests sitting around a circular table. Each guest has a unique ID with consecutive positive integers starting from 1. Initially, the guests are seated in a random order (each seat has exactly one guest) around the table. In one operation (which takes 1 second), you can choose an arbitrary subset of guests and simultaneously move each selected guest one seat either in the clockwise direction or in the anticlockwise direction. During an operation, a seat may become empty or may be occupied by more than one guest.

Your task is to determine the minimum number of seconds required so that after performing some operations, every seat is again occupied by exactly one guest and the guests’ IDs are arranged consecutively in order (either in clockwise or anticlockwise direction). In other words, if you choose some seat as the starting point, the guest IDs in the clockwise (or anticlockwise) order of the seats should be 1, 2, …, n.

Note on Movement: In each second, each moving guest shifts by exactly one seat. You can move different guests in different directions concurrently.

inputFormat

The first line contains an integer n representing the number of guests.

The second line contains n distinct integers. These integers represent the guest IDs in the order they are seated in clockwise order around the table. The positions are considered to be numbered from 0 to n-1 in the given order.

outputFormat

Output a single integer — the minimum number of seconds required to rearrange the guests so that every seat is occupied by exactly one guest and the guest IDs appear in consecutive order (either clockwise or anticlockwise).

sample

4
3 1 2 4

1