Carlson has a set of n candy jars at home. The jars are numbered from 1 to n , the i -th of them contains a i candies. Carlson considers a set of jars to be cute if this set does not contain three jars with different numbers of sweets.
Carlson has an unlimited supply of sweets in his pockets, so he can add any number of candies to any jar. Help him determine the minimum total number of candies he needs to add to make the set of candy jars cute.
Input
The first line of the input contains a natural number n ( 1 ≤ n ≤ 10
5 ) — number of cans in Carlson's set.
The second line of the input contains n integers a i ( 0 ≤ a
i ≤ 10
9 ) — number of candies in jars. Neighboring numbers are separated from each other by one space.
Imprint
Print one number — the minimum total amount of candy that Carlson needs to add in order for the jar set to be cute.
Note
In the first test from the example, Carlson can add two candies to the first jar, and — one candy. Then in the first and fourth jars there will be 7 candies each, and in the second and third — 2 sweets each.
In the second test from the example, the set of jars is initially cute, no candy is required.
Examples
| # |
Input |
Output |
| 1 |
4
5 1 2 7
| 3 |
| 2 |
3
1 1 1
| 0 |