B. В погоне за призом
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы и ваш друг участвуете в телешоу «В погоне за призом».

В начале шоу n призов располагаются на прямой. i-й приз находится в позиции ai. Позиции всех призов различны. Вы начинаете в позиции 1, ваш друг — на позиции 106 (в этих двух позициях нет призов). Вам необходимо, работая сообща, собрать все призы в любом порядке за минимальное время.

Известно, что переход из x в x + 1 или x - 1 занимает ровно 1 секунду как у вас, так и у вашего друга. Вы достаточно тренировались, так что приз поднимаете мгновенно, если его позиция совпадает с вашей текущей (то же верно и для вашего друга). Количество взятых призов никак не влияет на вашу скорость (и скорость вашего друга).

Теперь вы обсуждаете стратегию, решаете, кто какие призы будет брать. Обратите внимание, что каждый приз должен быть взят либо вами, либо вашим другом.

За какое наименьшее число секунд можно собрать все призы?

Входные данные

В первой строке записано одно целое число n (1 ≤ n ≤ 105) — количество призов.

Во второй строке записаны n целых чисел a1, a2, ..., an (2 ≤ ai ≤ 106 - 1) — позиции призов. Никакие два приза не стоят на одной позиции. Позиции заданы в возрастающем порядке.

Выходные данные

Выведите одно целое число — минимальное число секунд, за которое удастся собрать все призы.

Примеры
Входные данные
3
2 3 9
Выходные данные
8
Входные данные
2
2 999995
Выходные данные
5
Примечание

В первом примере вы забираете все призы: берете первый в секунду 1, второй — в 2 и третий — в 8.

Во втором примере вы берете первый приз за 1 секунду, ваш друг берет другой за 5 секунд, вы делаете это одновременно, так что итоговое время получается 5.