CF938B.Run For Your Prize

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 106 (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?

你和你的朋友正在参加一档电视节目《为奖品奔跑》。

节目开始时，有 $ n $ 个奖品位于一条直线上。第 $ i $ 个奖品位于位置 $ a_i $。所有奖品的位置互不相同。你从位置 $ 1 $ 出发，你的朋友从位置 $ 10^6 $ 出发（这两个位置上均没有奖品）。你们需要作为一个团队，在最短的可能时间内按任意顺序收集全部奖品。

已知：你和你的朋友每秒恰好可从位置 $ x $ 移动到位置 $ x+1 $ 或 $ x-1 $。此外，你们经过充分训练，只要当前所在位置与某个奖品位置重合，即可瞬间拾取该奖品（你的朋友同理）。携带奖品完全不会影响你或你朋友的移动速度。

现在，你们可以事先与朋友商讨策略，并决定每个奖品由谁拾取。注意：每个奖品必须被拾取，且只能由你或你的朋友中的一人拾取。

拾取全部奖品所需的最短时间（以秒为单位）是多少？

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

The second line contains n integers _a_1, _a_2, ..., a__n (2 ≤ a__i ≤ 106 - 1) — the positions of the prizes. No two prizes are located at the same position. Positions are given in ascending order.

第一行包含一个整数 $n$（$1 \leq n \leq 10^5$）—— 奖品的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$2 \leq a_i \leq 10^6 - 1$）—— 奖品的位置。任意两个奖品不会位于同一位置。位置按升序给出。

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

输出一个整数——收集所有奖品所需的最少秒数。

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.

在第一个例子中，你领取了所有奖品：第一个在时刻 1 领取，第二个在时刻 2 领取，第三个在时刻 8 领取。

在第二个例子中，你在 1 秒时领取第一个奖品，而你的朋友在 5 秒内领取其余奖品；你们同时进行，因此总时间为 5。