Minimizing Maximum Movement on a Circular Table

On Byteman’s birthday, there are (n) children (numbered from 1 to (n)) attending his party and sitting around a circular table with (n) chairs. Initially, the children sit in arrival order: child 1 picks an arbitrary seat; then child 2 sits immediately to the left of child 1; then child 3 sits to the left of child 2; and so on. In this way, the children end up sitting consecutively in the order of 1, 2, 3, (\dots), (n) around the table.\n\nHowever, Byteman’s parents want to reseat them in a specific circular order to avoid too much noise when troublesome children sit together. The desired seating is given as a permutation (p_1, p_2, \dots, p_n) (a rearrangement of (1) to (n)). In the new seating arrangement, child (p_1) will sit between (p_2) and (p_n); for every (2\le i\le n-1), child (p_i) sits between (p_{i-1}) and (p_{i+1}); and child (p_n) sits between (p_{n-1}) and (p_1). Note that the relative positions of (p_1) and (p_n) with respect to each other can be swapped, so there are two possible clockwise orders: either (p_1, p_2, \dots, p_n) or (p_1, p_n, p_{n-1}, \dots, p_2).\n\nTo make the reseating, each child must move some number of seats to the left or right along the circle. Their individual movement is measured by the minimum number of chairs traversed along the circle (i.e. the circular distance). The overall "messiness" is defined as the maximum movement distance among all children. Byteman’s parents want to reseat the children while minimizing this maximum movement distance.\n\nGiven (n) and the permutation (p_1, p_2, \dots, p_n), your task is to compute the minimum possible messiness value.\n\nNote:\n1. The initial seating is determined by the order of arrival. Assume that the children initially occupy positions (0, 1, \dots, n-1) in order (child (i) sits at position (i-1)).\n2. In the new seating, the children must occupy (n) consecutive seats (modulo (n)). If we fix a starting seat (S) (with (0 \le S < n)), then if the target seating order is (T[0], T[1], \dots, T[n-1]) (one of the two possibilities given above), child (T[j]) will occupy seat ((S + j) \bmod n).\n3. The movement distance for a child moving from an initial seat (a) to a new seat (b) is (\min(|a - b|, n - |a-b|)).\n\nDetermine the minimum maximum movement distance (messiness) achievable by appropriately choosing the reseating rotation and by selecting one of the two valid target orders.

inputFormat

The input is read from standard input and consists of two lines.\n\nThe first line contains a single integer (n) (the number of children).\n\nThe second line contains (n) space-separated integers (p_1, p_2, \dots, p_n) representing the desired permutation order.

outputFormat

Output a single integer — the minimum possible messiness value (i.e. the minimal maximum number of seats any child must move).

sample

4
1 2 3 4

0