Mock CCC '20 Contest 2 S4 - Rotational Arrays

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 0.5s
Memory limit: 256M

Problem types

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?

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.


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

1 2 2 2

Sample Output


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.


There are no comments at the moment.