{"raw_statement":[{"iden":"statement","content":"You and your friend are participating in a TV show \"Run For Your Prize\".\n\nAt 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.\n\nYou 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.\n\nNow 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.\n\nWhat is the minimum number of seconds it will take to pick up all the prizes?"},{"iden":"input","content":"The first line contains one integer _n_ (1 ≤ _n_ ≤ 105) — the number of prizes.\n\nThe 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."},{"iden":"output","content":"Print one integer — the minimum number of seconds it will take to collect all prizes."},{"iden":"examples","content":"Input\n\n3\n2 3 9\n\nOutput\n\n8\n\nInput\n\n2\n2 999995\n\nOutput\n\n5"},{"iden":"note","content":"In the first example you take all the prizes: take the first at 1, the second at 2 and the third at 8.\n\nIn 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."}],"translated_statement":[{"iden":"statement","content":"你和你的朋友正在参加一档电视节目《为奖品奔跑》。\n\n节目开始时，有 #cf_span[n] 个奖品位于一条直线上。第 #cf_span[i] 个奖品位于位置 #cf_span[ai]。所有奖品的位置互不相同。你从位置 #cf_span[1] 出发，你的朋友从位置 #cf_span[106] 出发（这两个位置上都没有奖品）。你们需要作为团队合作，在最短时间内收集所有奖品，顺序任意。\n\n你知道，从位置 #cf_span[x] 移动到位置 #cf_span[x + 1] 或 #cf_span[x - 1] 恰好需要 #cf_span[1] 秒，你和你的朋友都是如此。你们也经过充分训练，可以立即捡起位于当前位置的任何奖品（你的朋友也是如此）。携带奖品不会影响你们的速度（或你朋友的速度）。\n\n现在你可以与朋友讨论策略，决定由谁来捡起每个奖品。记住，每个奖品都必须由你或你的朋友之一捡起。\n\n收集所有奖品所需的最少秒数是多少？\n\n第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 105]) —— 奖品的数量。\n\n第二行包含 #cf_span[n] 个整数 #cf_span[a1], #cf_span[a2], ..., #cf_span[an] (#cf_span[2 ≤ ai ≤ 106 - 1]) —— 奖品的位置。没有两个奖品位于相同位置。位置按升序给出。\n\n请输出一个整数——收集所有奖品所需的最少秒数。\n\n在第一个例子中，你收集了所有奖品：在 #cf_span[1] 处捡起第一个，在 #cf_span[2] 处捡起第二个，在 #cf_span[8] 处捡起第三个。\n\n在第二个例子中，你在 #cf_span[1] 秒内捡起第一个奖品，你的朋友在 #cf_span[5] 秒内捡起另一个奖品，你们同时进行，因此总时间为 #cf_span[5]。"},{"iden":"input","content":"第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 105]) —— 奖品的数量。第二行包含 #cf_span[n] 个整数 #cf_span[a1], #cf_span[a2], ..., #cf_span[an] (#cf_span[2 ≤ ai ≤ 106 - 1]) —— 奖品的位置。没有两个奖品位于相同位置。位置按升序给出。"},{"iden":"output","content":"请输出一个整数——收集所有奖品所需的最少秒数。"},{"iden":"examples","content":"输入\n3\n2 3 9\n输出\n8\n\n输入\n2\n2 999995\n输出\n5"},{"iden":"note","content":"在第一个例子中，你收集了所有奖品：在 #cf_span[1] 处捡起第一个，在 #cf_span[2] 处捡起第二个，在 #cf_span[8] 处捡起第三个。在第二个例子中，你在 #cf_span[1] 秒内捡起第一个奖品，你的朋友在 #cf_span[5] 秒内捡起另一个奖品，你们同时进行，因此总时间为 #cf_span[5]。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of prizes.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a strictly increasing sequence of prize positions, where $ 2 \\le a_i \\le 10^6 - 1 $.  \nYou start at position $ 1 $; your friend starts at position $ 10^6 $.  \n\n**Constraints**  \n1. $ 1 \\le n \\le 10^5 $  \n2. $ a_i < a_{i+1} $ for all $ i \\in \\{1, \\dots, n-1\\} $  \n3. All $ a_i $ are distinct integers in $ [2, 10^6 - 1] $  \n\n**Objective**  \nPartition the set of prizes into two subsets: one collected by you (starting at 1), the other by your friend (starting at $ 10^6 $).  \nLet $ S \\subseteq \\{1, \\dots, n\\} $ be the set of indices of prizes collected by you, and $ T = \\{1, \\dots, n\\} \\setminus S $ the rest collected by your friend.  \n\nThe time you take is $ \\max_{i \\in S} (a_i - 1) $ if $ S \\neq \\emptyset $, else 0.  \nThe time your friend takes is $ \\max_{j \\in T} (10^6 - a_j) $ if $ T \\neq \\emptyset $, else 0.  \n\nThe total time is $ \\max\\left( \\max_{i \\in S} (a_i - 1), \\max_{j \\in T} (10^6 - a_j) \\right) $.  \n\nMinimize this maximum time over all possible partitions $ (S, T) $.  \n\nThat is, compute:  \n$$\n\\min_{S \\subseteq \\{1,\\dots,n\\}} \\max\\left( \\max_{i \\in S} (a_i - 1), \\max_{j \\notin S} (10^6 - a_j) \\right)\n$$","simple_statement":null,"has_page_source":false}