Say , size of given array is $$$N$$$ and $$$abs(a[i])$$$<= 10000000

Example :

$$$ {1,100,100,100,100} $$$

Minimum cost = 4

$$${1,100,101,99,102}$$$

I am looking for both $$$O(n*n)$$$ and $$$O(n)$$$ solutions .

Source of the problem : Just occurred to my mind .