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 < \max(2, 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?
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 the minimum number of modifications needed to convert ~a~ to a rotational array.
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~.
4 1 2 2 2
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.