You and your friend are participating in a TV show "Run For Your Prize".

At the start of the show n prizes are located on a straight line. i-th prize is located at position a_{i}. Positions of all prizes are distinct. You start at position 1, your friend — at position 10^6 (and there is no prize in any of these two positions). You have to work as a team and collect all prizes in minimum possible time, in any order.

You know that it takes exactly 1 second to move from position x to position x + 1 or x - 1, both for you and your friend. You also have trained enough to instantly pick up any prize, if its position is equal to your current position (and the same is true for your friend). Carrying prizes does not affect your speed (or your friend's speed) at all.

Now you may discuss your strategy with your friend and decide who will pick up each prize. Remember that every prize must be picked up, either by you or by your friend.

What is the minimum number of seconds it will take to pick up all the prizes?


-----Input-----

The first line contains one integer n (1 ≤ n ≤ 10^5) — the number of prizes.

The second line contains n integers a_1, a_2, ..., a_{n} (2 ≤ a_{i} ≤ 10^6 - 1) — the positions of the prizes. No two prizes are located at the same position. Positions are given in ascending order.


-----Output-----

Print one integer — the minimum number of seconds it will take to collect all prizes.


-----Examples-----
Input
3
2 3 9

Output
8

Input
2
2 999995

Output
5



-----Note-----

In the first example you take all the prizes: take the first at 1, the second at 2 and the third at 8.

In the second example you take the first prize in 1 second and your friend takes the other in 5 seconds, you do this simultaneously, so the total time is 5.

Difficulty: interview

Starter code:

Solutions:
n = int(input())
a = list(map(int, input().split()))
e = 1000000
ans = max(min(x - 1, e - x) for x in a)
print(ans)


n = int(input())
a = list(map(int, input().split()))
d = []
for i in a:
	d.append(min(i - 1, 10**6 - i))
print(max(d))

n = int(input())
a = list(map(int, input().split()))

maxd = 0
for i in range(n):
    if a[i] <= 500000:
        maxd = max(maxd, a[i] - 1)
    else:
        maxd = max(maxd, 1000000 - a[i])
print(maxd)

n = int(input())
v = [int(x) for x in input().split()]
Max = 0
for x in v:
	Max = max(Max, min(x - 1, 1000000 - x))
print(Max)


n=int(input())
el=map(int,input().split())
ans=0
for x in el:
    ans=max(ans,min(x-1,1000000-x))
print(ans)

n = int(input())
prizes = list(map(int, input().split()))

res = 0
for pos in prizes:
  res = max(res, min(pos-1, 10**6-pos))

print(res)


v = 'aiouey'
n = int(input())
a = list(map(int,input().split()))
fr = 1000000
mi = 0
for i in a:
    mi = max(min(fr-i,i-1),mi)
print(mi)


n = int(input())
pr = [int(x) for x in input().split()]
sec = 0
for elem in pr:
    you = elem - 1
    fri = 10 ** 6 - elem
    sec = max(sec, min(you, fri))
print(sec)


def main():
    n = int(input())
    a = [int(x) for x in input().split()]
    mm = 0
    for aa in a:
        m = min(aa - 1, 1000000-aa)
        mm=max(mm,m)
    print(mm)

    
def __starting_point():
    main()

__starting_point()

n = int(input())
a = list(map(int, input().split()))
res = min(a[-1] - 1, 10**6 - a[0])


for i in range(n - 1):
    res = min(res, max(a[i] - 1, (10**6 - a[i + 1])))
print(res)

import math as mt
import itertools as it
import functools as ft

stdin = lambda type_ = "int", sep = " ": list(map(eval(type_), input().split(sep)))
joint = lambda sep = " ", *args: sep.join(str(i) if type(i) != list else sep.join(map(str, i)) for i in args)

n = int(input())
a = stdin()
ans = 10**6 - a[0]

for i in range(n):
    ans = min(ans, max(a[i] - 1, 10**6 - (a[i + 1] if i != n - 1 else 10**6)))

print(ans)

def ii():
    return int(input())
def mi():
    return map(int, input().split())
def li():
    return list(mi())

n = ii()
a = li()
m = 10 ** 6 // 2
x = 0
y = 10 ** 6
for ai in a:
    if ai <= m:
        x = max(x, ai)
    else:
        y = min(y, ai)
ans = max(x - 1, 10 ** 6 - y)
print(ans)

n = int(input())
p = list(map(int, input().split()))

ans = 0
for val in p:
    ans = max(ans, min(abs(1 - val), abs(10**6 - val)))
print(ans)


import sys, math

#f = open('input', 'r')
f = sys.stdin
n = f.readline()
s = list(map(int, f.readline().split()))


print(max(min(x-1, 1000000-x) for x in s))


n = int(input())
l = list(map(int, input().split()))
ans = 0
for i in range(n):
    if min(l[i] - 1, 10 ** 6 - l[i]) > ans:
        ans = min(l[i] - 1, 10 ** 6 - l[i])
print(ans)

n = int(input())
print(max([min(int(x)-1, 10**6-int(x)) for x in input().split()]))

n = int(input())
d = list(map(int, input().split()))

res = 0
for x in d:
    res = max(res, min(x-1, 1000000-x))

print(res)


n = int(input())
a = list(map(int, input().split()))


middle = 500000

ans = -1

for pr in a:
    ans = max(ans, min(pr - 1, 1000000 - pr))

print(ans)


import sys

n = int(sys.stdin.readline())
data = list(map(int, sys.stdin.readline().split()))

ans = min(data[-1] - 1, 1000000 - data[0])
for i in range(n - 1):
    cur_ans = max(data[i] - 1, 1000000 - data[i + 1])
    ans = min(ans, cur_ans)
print(ans)


n=int(input())
a=[int(i) for i in input().split()]

ans=0
for num in a:
	tmp=min(num-1,10**6-num)
	ans=max(ans,tmp)
print(ans)


n = int(input())
a = [int(i) for i in input().split()]
a = [1] + a + [10**6]
mx = 10**6
for i in range(len(a) - 1):
    mx = min(mx, max(a[i] - a[0], a[-1] - a[i + 1]))
print(mx)


n = int(input())
a = list(map(int, input().split()))
b = 500000.5
if a[0] > b:
    print(10 ** 6 - a[0])
    return
if a[n - 1] < b:
    print(a[n - 1] - 1)
    return
i = 0
while i < n - 1 and not (a[i] < b < a[i + 1]):
    i += 1
print(max(a[i] - 1, 10 ** 6 - a[i + 1]))

n=int(input())
niz=list(map(int,input().split()))
poz1=1
poz2=10**6
vreme=0
for nagrada in niz:
    tr1=nagrada-poz1
    tr2=poz2-nagrada
    vreme=max(vreme,min(tr1,tr2))
print(vreme)

n = int(input())
line = input()
a = [int(x) for x in line.split()]

result = max([min(x-1, 1000000-x) for x in a])

print(result)


import sys

def main():
    n = int(input())
    ar = list(map(int, input().split()))
    ar.extend([1, 10**6])
    ar.sort()
    
    print(min([max(ar[i] - 1, 10**6 - ar[i + 1]) for i in range(len(ar) - 1)]))

    
        
def __starting_point():
    main()

__starting_point()