For the sequence to become an arithmetic sequence, we need the differences between adjacent elements to be equal. This motivates us to consider the difference array ~D~, where ~D_i = A_{i+1} - A_i~ for ~1 \le i < N~. We can now ignore array ~A~. There are three possible types of operations:

1. The entire array is shifted. Then, ~D~ is unaffected.
2. Either the first or the last element of the array is part of the shifted array, but not both. Then, exactly one element of ~D~ increases or decreases by ~1~.
3. Neither the first nor the last element of the array is part of the shifted array. Then, exactly one element of ~D~ is increased by ~1~, and exactly one element of ~D~ is decreased by ~1~.

Suppose that we want all elements of ~D~ to be equal to ~X~, and let ~S~ be the number of operations needed for this to occur. It would be useful to find a formula for ~S~. A natural step is to separately consider the elements of ~D~ greater than ~X~, and the elements of ~D~ less than ~X~. Let ~U~ be the sum of ~(D_i - X)~ for all ~D_i \ge X~, and let ~L~ be the sum of ~(X - D_i)~ for all ~D_i < X~. We can think of ~U~ and ~L~ as the number of decrements and increments needed, respectively, in order for all elements of ~D~ to be equal to ~X~. Note that:

• A lower bound of ~S~ is ~\max(U, L)~. This is because each operation can decrease ~U~ by at most ~1~, and decrease ~L~ by at most ~1~.
• An upper bound of ~S~ is ~\max(U, L)~. This is because we can repeatedly pair one increment with one decrement using a type ~2~ operation. If we run out of increments or decrements, we can use type ~3~ operations instead.

It follows that ~S = \max(U, L)~.

Now, we should try to find the optimal value of ~X~. Observe that as ~X~ increases, ~U~ decreases while ~L~ increases. This means that ~S~ is minimised when ~U~ and ~L~ are approximately equal. It's possible to compute ~X~ immediately using a binary search, but there is a more direct formula. Let ~A~ be the number of elements of ~D~ greater than or equal to ~X~, and let ~B~ be the number of elements of ~D~ smaller than ~X~, so that ~A + B = N-1~. In order for ~U~ and ~L~ to be equal, we would require:

$$\displaystyle U = L$$

$$\displaystyle \sum_{D_i \ge X} (D_i - X) = \sum_{D_i < X} (X - D_i)$$

$$\displaystyle (\sum_{D_i \ge X} D_i) - XA = XB - (\sum_{D_i < X} D_i)$$

$$\displaystyle X(A+B) = (\sum_{D_i \ge X} D_i) + (\sum_{D_i < X} D_i)$$

$$\displaystyle X(N-1) = \sum D_i$$

$$\displaystyle X = \frac{\sum D_i}{N-1}$$

This means that the optimal value of ~X~ is the mean of ~D~. This should make sense intuitively as well, considering the mean as some kind of equilibrium value. (Indeed, it is directly analagous to clockwise torque being equal to anticlockwise torque around the centre of mass.) If the mean is not an integer, we should try both rounding the mean down as well as up. Computing the value of ~S~ using our formula yields the correct answer. Be careful of the special case where ~N = 1~ as the mean of an empty sequence is undefined.

Time complexity: ~\mathcal{O}(N)~ or ~\mathcal{O}(N\log({\max{|A|}}))~