Limits
1s, 512 MB

Rakib & Raghib are two friends. One day Rakib gave an array of numbers to Raghib and told him to make it beautiful.

To make it beautiful it needs to fulfill these two conditions:

1.All the numbers in the array should be unique.

2.And after making all the numbers unique he wants to make the difference between the smallest & largest number in the array equal to (length of array-1).

Suppose {1,2,3,4,5},{3,2,4,5} both are beautiful but {1,2,3,4,6} is not beautiful.

To make it beautiful we can replace a number with any number.

Here Rakib told Raghib to make it beautiful and asked him how many operations are needed to make it beautiful. Just return the minimum number of operations to make it beautiful.

So now Raghib needs your help. Can you help him?

The first line contains an integer n(2<=n<=10^5) - the size of the array. The second line contains n numbers where A[i] indicates the value of ith position (1<=A[i]<=10^9).

For each case print a single integer that denotes the minimum number of operations need to make the array beautiful.

Input | Output |
---|---|

5 1 2 3 4 5 | 0 |

Input | Output |
---|---|

5 1 2 3 4 6 | 1 |

**For the first sample**

Here all the values are unique. And maximum value of array (5)-minimum value of array(1)=array length-1 (4). So we don’t need any operation because it is already beautiful.

**But for the second sample**

All the values are unique. But maximum value of array (6)-minimum value of array(1) =5 which is not equal to the array length-1(4). So we need only one operation to change 6 to 5 to make it beautiful. After changing the value 6 to 5 then the array looks {1,2,3,4,5}.

Login to submit.

29%
Solution Ratio

Guess.WhoEarliest,

Cloud_Fastest, 0.0s

Cloud_Lightest, 5.7 MB

user.338682Shortest, 795B

Toph uses cookies. By continuing you agree to our Cookie Policy.