CF938B Run For Your Prize

你和你的朋友正在参加电视节目“Run For Your Prize”。 在节目开始时，有 $n$ 个奖品被放置在一条直线上。第 $i$ 个奖品位于位置 $a_{i}$。所有奖品的位置都不相同。你从位置 $1$ 出发，你的朋友从位置 $10^{6}$ 出发（这两个位置都没有奖品）。你们需要合作，以任意顺序在最短时间内收集所有奖品。 你们知道，从位置 $x$ 移动到 $x+1$ 或 $x-1$ 都需要恰好 $1$ 秒，无论是你还是你的朋友。你们已经训练得足够熟练，只要当前位置等于奖品的位置，就能瞬间捡起奖品（你的朋友也是如此）。携带奖品不会影响你或你朋友的速度。 现在你可以和你的朋友讨论策略，决定每个奖品由谁来捡。请记住，每个奖品都必须被捡起，可以由你或你的朋友完成。 请问，收集所有奖品所需的最少秒数是多少？

第一行包含一个整数 $n$（$1 \leq n \leq 10^{5}$），表示奖品的数量。 第二行包含 $n$ 个整数 $a_{1}, a_{2}, \ldots, a_{n}$（$2 \leq a_{i} \leq 10^{6}-1$），表示奖品的位置。没有两个奖品在同一个位置。位置按升序给出。

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

在第一个样例中，你收集所有奖品：第一个在 $1$，第二个在 $2$，第三个在 $8$。 在第二个样例中，你用 $1$ 秒收集第一个奖品，你的朋友用 $5$ 秒收集另一个奖品，你们可以同时进行，因此总时间为 $5$ 秒。 由 ChatGPT 4.1 翻译