HearthStone

Alice loves playing HearthStone. She likes the Warlock hero class, which can cast the spell Defile. When cast, Defile deals $1$ unit of damage to the health of all minions. If any minion dies, Defile is cast again automatically. If two or more minions die at the same time, Defile is still cast only once. That cast may kill other minions, which causes Defile to be cast again, and so on. The health of each minion is a nonnegative integer. A minion dies when its health becomes zero. When a minion dies, it disappears and does not die twice. There are $n$ minions. Before casting Defile, Alice can take zero or more steps. In each step, Alice changes the health of one minion by one. If a minion has health $x$, Alice can change it to $x-1$ or $x+1$. Alice wants to find the minimum number of steps needed so that she can cast Defile once and kill all the minions.

The first line contains a single integer $n$ ($1 \leq n \leq 10^6$). The next line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^6$), the health of the $n$ minions.

Print one integer: the minimum number of steps before Alice can cast a single Defile to kill all the minions.