您和您的朋友正在参加电视节目“为你的奖品奔跑”。
在节目开始时,n 个奖品位于一条直线上。第 i 个奖品位于位置 ai。所有奖品的位置各不相同。你从位置 1 开始,你的朋友从位置 106 开始(这两个位置都没有奖励)。您必须作为一个团队合作,并在尽可能短的时间内以任何顺序收集所有奖品。
您知道,对于您和您的朋友来说,从位置 x 移动到位置 x + 1 或 x - 1 都需要 1 秒。如果奖品的位置与您当前的位置相同(您的朋友也是如此),您也已经接受了足够的训练,可以立即获得任何奖品。携带奖品完全不会影响你的速度(或你朋友的速度)。
现在您可以与您的朋友讨论您的策略并决定谁将获得每个奖品。请记住,每个奖品都必须由您或您的朋友领取。
领取全部奖品最少需要多少秒?
输入
第一行包含一个整数 n (1 ≤ n ≤ 105) — 奖品数量。
第二行包含 n 个整数 a1, a2, ..., an (2 ≤ ai ≤ 106 - 1) — 奖品的位置。没有两个奖品位于同一位置。职位按升序排列。
输出
打印一个整数——收集所有奖品所需的最短秒数。
示例
输入 #1
3 2 3 9
输出 #1
8
输入 #2
2 2 999995
输出 #2
5
注意
在第一个示例中,您获得了所有奖品:第一个奖品为 1,第二个奖品为 2,第三个奖品为 8。
在第二个例子中,你在 1 秒内获得了第一个奖品,而你的朋友在 5 秒内获得了另一个奖品,你们同时这样做,所以总时间是 5。