该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

在一条坐标轴上，你$\red{x=1}$处，朋友在$\red{10^6}$处，你们两中间

有 $\red{n}$个礼物第$\red{i}$ 个礼物坐标为$\red{a_i(1<a_i<10^6)}$,

现在你们同时出发，且每秒可以移动一个单位。

一个经过某个礼物，你或你的朋友就会捡起它，请问把所有礼物捡起最少要多少秒。

输入格式

共两行。

第一行一个正整数$\red{ n}$表示礼物的个数。

第二行 $\red{n}$个整数表示 $\red{n}$个礼物的位置。

输出格式

一个整数，表示最少需要多少秒

样例

输入样例1

3
2 3 9

输出样例1

8

输入样例2

2
2 999995

输出样例

5

提示

对于$\red{30\%}$的数据，有$\red{1=<n<=1000}$

对于$\red{100\%}$的数据，有$\red{1=<n<=100,000 , 1<a_i<1000,000}$