CONGA  Conga line
Conga is a traditional dance in which people make a line, grab each other by the waist and start dancing around.
You are at a party and your favorite Conga song starts playing. Since you want to make the most of it, you'd like to organize everybody and start dancing as soon as possible.
The dance floor is modeled as an infinite straight line with people standing on positive integer coordinates. There is at most one person at each point. Every second, a person can move one unit to the left or one unit to the right, as long as no one else is standing there. However, since it's a crazy party and people are already drunk, at most one person can move every second (in other words, no two people can move simultaneously).
Nobody will start dancing until everybody is organized in a perfect line. You want to find the minimum amount of time it takes to start dancing, i.e. the time it takes to make people stand in such a way that there are no empty spaces between them.
For example, imagine there are 4 people at the party, standing at positions 2, 4, 5 and 8:
In this case, it takes at least 3 seconds to form the Conga line:
 On second 1, the person standing at position 2 moves to position 3.
 On second 2, the person standing at position 8 moves to position 7.
 On second 3, the person standing at position 7 moves to position 6.
 After three seconds, people are standing on positions 3, 4, 5, and 6 and they can start dancing!
Input
The input contains several test cases.
The first line of each case contains a single integer number n, the number of people in the party (1 ≤ n ≤ 10^{6}). The next line contains n distinct integers x_{i} separated by single spaces sorted in ascending order — the coordinates where people are initially standing (1 ≤ x_{i} ≤ 10^{9}).
The last line of the input contains a single 0 and should not be processed.
Output
For each test case, output one integer number on a single line — the minimum time it takes to start dancing.
Example
Input: 4
2 4 5 8
1
10
4
20 24 25 26
2
1 2
2
1 1000000000
0 Output: 3
0
3
0
999999998
hide comments
Piyush Kumar:
20160610 07:19:41
The time limit is too strict. cin,cout can't pass! 

dwij28:
20160428 20:56:55
Got AC with C++. There is just 1 AC python solution for this problem in 0.86 seconds and that too by one of the best python guys, "numerix". Its really sad when O(n) solutions in python do not pass. What do people want to achieve by restricting us from coding simple things in a simple language ? 

shantanu tripathi:
20150809 19:55:35
haha.... kkkk @steven hans limantoro.. 

Steven Hans Limantoro:
20150809 15:28:50
It can be moved to tutorial, I guess.


shantanu tripathi:
20150809 13:07:36
finally accpted.:).. for the avg median is always better than mean ...if the arry is sorted ... 

agaurav77:
20140604 20:35:44
Bhavik, I agree. Finally AC! 

Rishav Goyal:
20140324 17:03:38
think naive way :)


anurag garg:
20140112 20:42:43
with int WA and with long long int AC 

Bhavik:
20140111 20:25:35
very nice problem...got deceived by the test cases 
Added by:  Paulo Costa 
Date:  20120114 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Universidad EAFIT (Colombia)  Brazilian ICPC Training Camp, JanFeb/2012 