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?

Input

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).

Output

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

Samples

InputOutput
5
1 2 3 4 5
0
InputOutput
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}.

Submit

Login to submit.

Statistics

47% Solution Ratio
Guess.WhoEarliest, Oct '22
Cloud_Fastest, 0.0s
nusuBotLightest, 4.9 MB
imAniksahAShortest, 585B
Toph uses cookies. By continuing you agree to our Cookie Policy.