CONGA - Conga line

no tags 

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 favourite 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 modelled 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:

Conga line

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!

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 ≤ 106). The next line contains n distinct integers xi separated by single spaces sorted in ascending order — the coordinates where people are initially standing (1 ≤ xi ≤ 109).

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: 2016-06-10 07:19:41

The time limit is too strict. cin,cout can't pass!

dwij28: 2016-04-28 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: 2015-08-09 19:55:35

haha.... kkkk @steven hans limantoro..

Steven Hans Limantoro: 2015-08-09 15:28:50

It can be moved to tutorial, I guess.
@Shantanu Tripathi : No spoiler please

shantanu tripathi: 2015-08-09 13:07:36

finally accpted.:).. for the avg median is always better than mean ...if the arry is sorted ...

agaurav77: 2014-06-04 20:35:44

Bhavik, I agree. Finally AC!

Rishav Goyal: 2014-03-24 17:03:38

think naive way :)
nice problem .

anurag garg: 2014-01-12 20:42:43

with int WA and with long long int AC

Bhavik: 2014-01-11 20:25:35

very nice problem...got deceived by the test cases


Added by:Paulo Costa
Date:2012-01-14
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, Jan-Feb/2012