An array ~a~ of ~N~ elements can be rotated to the right by taking the last element and moving it to the front. For example, rotating ~[1, 2, 3, 4]~ to the right once results in ~[4, 1, 2, 3]~.

An array is considered rotational if it can be rotated some number of times ~k~ to the right, where ~1 \le k < N~, and result in the original array. For example, the array ~[1, 1, 1]~ is considered rotational.

One modification of an array consists of increasing or decreasing an element's value by ~1~. Given an array ~a~, can you determine the minimum number of modifications needed in order to convert an array to a rotational array?

Input Specification

The first line will contain the integer ~N~ ~(1 \le N \le 10^5)~, the number of elements.

The second line will contain ~N~ integers, ~a_i~ ~(1 \le a_i \le 10^9)~, the elements of the array.

Output Specification

Output the minimum number of modifications needed to convert ~a~ to a rotational array.

Subtasks

For 3/15 of the points, ~N \le 10, a_i \le 2~.

For an additional 5/15 of the points, ~a_i \le 2~.

Sample Input

4
1 2 2 2

Sample Output

1

Explanation For Sample

We can increase the first element's value to ~2~, which transforms it into a rotational array. This is exactly one modification.