### PROBLEM LINK:

**Author:** Rishav Pati

**Tester:** Rajat De

**Editorialist:** Sidhant Bansal

**Difficulty :** Cakewalk - Easy

**Expected Complexity:** O(A_MAX * N * N)

**Editorial -**

The array should be an arithmetic progression with common difference 1, ie. more formally A[i] - A[i - 1] = 1, for all i from 2 to N

As N <= 50 and A[i] <= 50 we can do a naive brute force.

We can assume the first element to be from the values 0 to S where S is the sum of all the elements of array A[].

- For each starting element we build the entire AP of the array in O(N), let this array be B[] and check weather the sum of all these elements is equal to S.
- If Yes, then we can calculate the minm no. of steps to do this by maintaining a variable RESULT, initialize RESULT to 0.
- Wherever we find that B[i] > A[i], add (B[i] - A[i]) to RESULT.

Pseudocode -

```
ANSWER = INT_MAX
FOR i = 0 to S (where S is the sum of array A[])
B[ 1 ] = i
SUM = B [ 1 ]
FOR j = 2 to N
B[j] = B[j - 1] + 1
SUM = SUM + B[j]
IF SUM = S
RESULT = 0
FOR j = 1 to N
IF B[j] > A[j]
RESULT = RESULT + (B[j] - A[j])
ANSWER = MIN(ANSWER, RESULT)
IF ANSWER = INT_MAX
PRINT -1
ELSE
PRINT ANSWER
```

Complexity analysis - O(A_MAX * N * N), as S = A_MAX * N in the worst case and the checking of array B[] is O(N).