Skip to content
TheChatArchiveThe Chat Archive
DeepSeekDeepseek v3.2· deepseekHugging Face Frontier Reasoning Traces

You and your friend are participating in a TV show "Run For Your Prize". At the start of…

  1. User

    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 ai. 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? Input

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

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

    Output

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

    Examples

    Input

    3 2 3 9

    Output

    8

    Input

    2 2 999995

    Output

    5

    Note

    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.

  2. DeepSeek Assistant

    We are given a line from 1 to 10^6. You start at 1, friend starts at 10^6. There are n prizes at distinct positions a_i (sorted ascending). You both can move at speed 1 per second along integer positions, and can instantly pick up a prize when you are at its position. You can decide which prizes each person collects. Both can move simultaneously. The total time is the maximum of the times each person takes (since they operate in parallel) to complete their assigned collection? Actually, careful: The time to collect all prizes is the time until all prizes have been collected. Since they move simultaneously, the total time is the maximum of the times taken by each individual to finish their assigned tasks. But we are allowed to assign each prize to either person, and each person can start moving from their starting position at time 0. They can move in any order to collect their assigned set of prizes. For each person, the time to collect a set of prizes is the minimum possible time to start at their starting point, visit all assigned positions (order can be optimized), and then presumably they can stop after collecting all assigned prizes; they don't have to return anywhere. The total time is the maximum of the two completion times. We want to minimize that maximum.

    So the problem is to partition the set of prize positions into two subsets: one for you (starting at 1) and one for your friend (starting at 10^6). For each subset, the optimal route to collect them (starting from the respective start) is: since the positions lie on a line, and the start is at an endpoint (1 for you, 10^6 for friend), the optimal route to collect a set of positions is to go from the start to the farthest point in the subset (in terms of distance from start) but direction matters. For you starting at 1, moving to the right: your positions will be >1. Since you can move left and right, but all prizes are between 2 and 999999, and you start at the leftmost end. If you are assigned some subset of prizes, the optimal path to collect them all starting from 1 and ending anywhere (no need to return) is to go to the rightmost prize among your subset, possibly also going left? But you cannot go left because start is at 1 and all prizes are >=2. So you only move to the right. Since you can pick up prizes along the way, the minimal time to collect a set S (with all positions >=2) is simply the maximum position in S minus 1? Actually, you start at 1. If you go directly to the farthest prize, you will pass through all intermediate positions, but note that the set S might not be contiguous; there could be gaps where prizes are assigned to the friend. But you can skip those: you don't need to stop at positions that are not assigned to you. However, to go from one of your prizes to another that is further right, you may have to pass through positions that are not yours, but that's fine; you just move through them without stopping. So the minimal time to collect your assigned prizes is the maximum distance you need to travel from start to the farthest prize you are assigned, because you can start moving right, and you might need to sometimes go left? Consider if you have prizes at positions that are not monotonic? Actually, all positions are on a line, and you start at the leftmost end. If you are assigned a set of prizes that are not all to the right of each other? But they are all to the right of 1. So if you assign a set of prizes to you, you can simply go from 1 to the rightmost prize in your set, picking up your prizes as you pass them (you might need to deviate left? No, because if you have a prize at a position x, to pick it you need to be at x. If you are moving from 1 to some far right position R, you will pass through all positions between 1 and R, including x, so you can pick it when you are at x. So you don't need to go left. However, what if there is a prize to the left of some other prize but you want to go to a far right prize first then come back to a left one? That would be worse because you would have to backtrack. The optimal strategy is to go in one direction from start to the farthest assigned prize, because all prizes are on one side (to the right) of your start. So the minimal time to collect a set S is simply max(S) - 1 (since starting at 1, you need to reach the farthest position). But wait: if S is empty, then you have nothing to collect, so time = 0.

    Similarly, for your friend starting at 10^6, all prizes are to the left (since max prize position <= 10^6 - 1). So the optimal for friend is to go left from 10^6 to the smallest position in his assigned set. The time would be 10^6 - min(S_friend). Since friend starts at 10^6 and moves left, the distance to the farthest left assigned prize is 10^6 - min(S_friend). So time = 10^6 - min(S_friend). If friend's set is empty, time = 0.

    Thus, the problem reduces to: we have n points sorted ascending a1 < a2 < ... < an. We need to split them into two subsets: left subset (collected by you) and right subset (collected by friend). But note: assignment is not necessarily based on left/right split; you could assign some leftmost prizes to friend, but friend starts at 10^6, so if friend is assigned a prize far left, friend will have to travel a long distance (10^6 - that position). Similarly, you could assign far right prizes to you, which would make you travel far. The natural optimal assignment would likely assign some prefix of prizes to you and suffix to friend? Let's analyze: If you assign a prize at position x to you, your time is at least x-1 (if that is your farthest). If you assign it to friend, friend's time is at least 10^6 - x (if that is his nearest). Since both times affect the maximum, we want to balance these. There is no advantage to interleaving assignments because the times depend only on the maximum of assigned positions for you and minimum for friend. If you assign you a set that is not contiguous, your time is determined by the maximum among them. So if you take a prize at a relatively far right, your time becomes large; if you also take some left prizes, it doesn't reduce your time. Similarly, friend's time is determined by the minimum among his assigned set; if he takes a prize far left, his time becomes large. Therefore, to minimize the maximum, we would likely want to assign a contiguous block of leftmost prizes to you and the remaining rightmost prizes to friend. Because any assignment that gives you a prize at x and also gives friend a prize at y with y < x would be suboptimal? Let's examine: Suppose we have two prizes at positions p < q. If we assign p to you and q to friend, your time is at most q? Wait, your time is max of your assigned positions - 1. If you only have p, your time = p-1. Friend's time = 10^6 - q (since min of his set is q). If we swap: assign q to you and p to friend, then your time = q-1, friend's time = 10^6 - p. Which of these yields a lower max? It depends on values. The typical approach for such problems is to consider partitioning at some index k: you take first k prizes (the k smallest) and friend takes the rest (n-k prizes). But is it always optimal? Could we have an assignment where you take some left and some right but not all left? For instance, you take a1 and a3, friend takes a2. Then your time = max(a1, a3)-1 = a3-1; friend's time = 10^6 - min(a2, ... )? Actually friend's set includes a2 and maybe others; min = a2, so friend's time = 10^6 - a2. Compare to partition at k=2 (you take a1,a2; friend takes a3): your time = a2-1; friend's time = 10^6 - a3. Or partition at k=1: you take a1; friend takes a2,a3: your time = a1-1; friend's time = 10^6 - a2. Which is best? It depends. The assignment you take a1,a3 gives your time = a3-1, friend = 10^6 - a2. Typically, a3 > a2, so your time might be larger than if you took only a1. And friend's time may be larger if a2 is small. So this seems worse than partition at k=1 or k=2. But could there be a scenario where interleaving reduces max? Suppose positions: 500, 600, 700. You start at 1, friend at 1000. Partition at k=1: you time=499, friend time=1000-600=400 -> max=499. Partition at k=2: you time=599, friend time=1000-700=300 -> max=599. Partition at k=0 (you none): you time=0, friend time=1000-500=500 -> max=500. So best max=499. Now interleaving: you take 500 and 700, friend takes 600: you time=699, friend time=400 -> max=699 worse. You take 600, friend takes 500,700: you time=599, friend time=500 -> max=599. You take 700, friend takes 500,600: you time=699, friend time=500 -> max=699. So partition is best.

    Consider another: positions: 400, 800, 900. Partition at k=1: you 399, friend 1000-800=200 -> max=399. k=2: you 799, friend 100 -> max=799. k=0: you 0, friend 600? Actually friend min=400, so 600? Wait 1000-400=600 -> max=600. So best=399. Interleaving: you 400,900 -> you 899, friend 1000-800=200 -> max=899. Worse. So indeed partition seems optimal.

    But we need to ensure that any optimal assignment can be transformed into a partition where you take a prefix and friend takes suffix without increasing the maximum time. Formal reasoning: Since your time depends only on max assigned to you, and friend's time depends only on min assigned to friend, any assignment where there exists indices i<j such that you take a_j and friend takes a_i can be swapped? Let's consider swapping: if you take a_j and friend takes a_i, swapping would give you a_i and friend a_j. After swap, your new max = max( your other assigned max, a_i ) <= a_j? Not necessarily. But if a_i is smaller than a_j, your max might reduce, friend's min might increase (since a_j > a_i). Swapping typically reduces your max and increases friend's min, which could balance the max. Actually we want to minimize the maximum of the two times: T_you = max(S_you) - 1 (if nonempty else 0); T_friend = 10^6 - min(S_friend) (if nonempty else 0). Let M = max(T_you, T_friend). The objective is to minimize M.

    Consider assignment. Define x = max(S_you) if S_you not empty else 1? Actually if empty, T_you=0, but we can treat max as 1? Not needed. Define y = min(S_friend) if nonempty else 10^6? If empty, T_friend=0, we can think of min as 10^6? But careful. For simplicity, we can think of the decision: we choose a threshold t such that all prizes <= t go to you and > t go to friend? But since the sets can be interleaved, maybe an optimal assignment can be represented by a split point: all prizes with index <= k go to you, rest to friend. Let's prove: Suppose we have an optimal assignment. Let L = max index of prize assigned to you (if any), and R = min index of prize assigned to friend (if any). If there is no overlap, i.e., L < R, then it's a partition of prefix and suffix. If there is overlap, meaning there exist i < j such that i is assigned to friend and j is assigned to you, then we have L >= j and R <= i, so L >= R. Actually if there is such pair, then the max index assigned to you is at least j, and the min index assigned to friend is at most i, so indeed max_you_index >= min_friend_index. In other words, the sets are not separated by index. In that case, we can try to reassign to improve. Since a_i < a_j, we have T_you >= a_j - 1, T_friend >= 10^6 - a_i. Suppose we swap assignments: give a_i to you and a_j to friend. Then new T_you' = max( previous max among your other prizes except a_j, a_i ) - 1. Since a_i < a_j, this max is <= previous max (unless your max came from another prize > a_j, then unchanged). So T_you' <= T_you. Similarly, new T_friend' = 10^6 - min( previous min among friend's other prizes except a_i, a_j ) . Since a_j > a_i, the new min is at least a_i? Actually friend's min originally was min(..., a_i, ...) = at most a_i. After swapping, we remove a_i and add a_j, so new min = min(previous min except a_i, a_j). Since a_j > a_i, the new min could be higher if a_i was the original min. So T_friend' <= T_friend? Wait careful: originally T_friend = 10^6 - m, where m = min(S_friend). Since a_i is in S_friend, m <= a_i. After swapping, a_i is removed, and a_j is added. So the new min m' = min( (S_friend \ {a_i}) ∪ {a_j} ). Since a_j > a_i, it's possible that the original min was some other element smaller than a_i, in which case m' = that same element, so unchanged. If a_i was the unique min, then m' = min( other elements, a_j ), which is > a_i (since all other elements are > a_i because a_i was min). So m' > a_i, hence T_friend' = 10^6 - m' < 10^6 - a_i = T_friend (if a_i was the min). So T_friend' <= T_friend. In either case, T_friend' is not larger than T_friend? Actually if a_i was not the min, then m' = original m, so T_friend' = T_friend. So swapping does not increase T_friend; it either decreases or stays same. And T_you' does not increase (it may decrease). Therefore, after swapping, the maximum of the two times does not increase; it could stay same or decrease. So we can repeatedly swap such cross assignments until there is no crossing: i.e., all your prizes have indices less than all friend's prizes. Hence an optimal assignment exists that is a prefix for you and suffix for friend. (Edge case: one of the sets could be empty.)

    Thus we can assume we choose a split index k from 0 to n: you take the first k prizes (positions a1..ak) and friend takes the remaining n-k prizes (a_{k+1}..a_n). If k=0, you take none; if k=n, friend takes none.

    Now compute times: T_you = if k>0 then a_k - 1 else 0. T_friend = if k<n then 10^6 - a_{k+1} else 0. Total time = max(T_you, T_friend). We need min over k of that max.

    But wait: Is that correct? For friend, when he takes suffix from a_{k+1} to a_n, his time is the distance from 10^6 to the leftmost of his set, which is a_{k+1}. So indeed T_friend = 10^6 - a_{k+1} if k < n, else 0. But what if friend has multiple prizes? He might need to go further left than the leftmost? Since he starts at 10^6 and moves left, to collect all his assigned prizes, he must go at least to the leftmost assigned prize (the smallest position). But he might also need to go to some positions that are to the right of that leftmost? Actually he must collect all prizes in his set. All his assigned positions are >= a_{k+1} and <= a_n. Starting from 10^6, if he goes directly to the leftmost assigned prize (a_{k+1}), he will pass through all larger positions on the way (since moving left, positions decrease). However, note that his assigned positions are all to the left of his start, but they are in increasing order as he moves left? Starting at 10^6, as he moves left, the positions he encounters are decreasing: 10^6-1, 10^6-2, ... So if his assigned set includes some positions that are not contiguous, but all are less than 10^6, then moving from 10^6 to the leftmost will pass through all intermediate integer positions, which includes all assigned prizes because they lie between a_{k+1} and 10^6. However, careful: If he goes directly to the leftmost prize, he will pass through positions in descending order. But his assigned prizes are in ascending order (a_{k+1} < a_{k+2} < ... < a_n). When moving from 10^6 down to a_{k+1}, he passes through all positions from 10^6-1 down to a_{k+1}+1 and then a_{k+1}. Does that guarantee he passes through a_{k+2}? Yes, because a_{k+2} is larger than a_{k+1} (since sorted). When moving from 10^6 to a_{k+1}, you will pass through all positions greater than a_{k+1} up to 10^6. Since a_{k+2} > a_{k+1}, you will pass through a_{k+2} before reaching a_{k+1} (since you are moving leftwards, you'll hit the larger numbers first). Actually: Starting at 10^6, as you move left, you go to 10^6-1, 10^6-2, ... eventually you hit a_n, then a_{n-1}, ... down to a_{k+1}. So you will encounter all prizes in the suffix in descending order. So indeed, going to the leftmost prize suffices to collect all. So friend's time = 10^6 - a_{k+1}. Similarly, your time = a_k - 1.

    But wait: Could there be a better strategy where friend goes to some prize not the leftmost first, then goes back? That would be longer. So yes.

    Thus, we just need to compute min_{k=0..n} max( (k>0 ? a_k - 1 : 0), (k<n ? 10^6 - a_{k+1} : 0) ).

    Also note that if k=0, T_you = 0, T_friend = 10^6 - a_1? Actually if you take none, friend takes all, so T_friend = 10^6 - a_1 (since leftmost of all is a_1). That's consistent: a_{k+1}=a_1. Similarly, if k=n, T_you = a_n - 1, T_friend = 0.

    Now, we need to consider that both can move simultaneously, but the time is the max of their individual times. So the answer is that min over splits.

    But is there any scenario where it's better for one person to also collect prizes on the other side? For example, you might go right to collect some, then turn back to collect others? That would be slower than just going to the farthest, because turning back would add extra distance. Since you start at the extreme end, it's always optimal to go straight to the farthest prize in your set and not turn back, as argued. So the above is correct.

    Now we need to implement: read n, read array a sorted. Compute ans = min over k as described.

    But careful: The times are in seconds. The positions are integers, and movement is 1 per second. Starting positions are 1 and 10^6. So a_k - 1 and 10^6 - a_{k+1} are integers.

    Edge cases: n=1. Then we consider k=0 and k=1. For k=0: T_you=0, T_friend=10^6 - a1. For k=1: T_you=a1-1, T_friend=0. The answer is min( max(0,10^6-a1), max(a1-1,0) ) = min(10^6-a1, a1-1). That matches expectation: either you collect it or friend does, whichever is faster. Since both start at extremes, the time is distance from the closer person? Actually not exactly, because if you collect it, you take a1-1 seconds; if friend collects, takes 10^6-a1 seconds. So the better is the smaller. So answer is min(a1-1, 10^6-a1). But is that always optimal? Yes, because they can work simultaneously but only one prize, so one person collects and the other does nothing. So total time is the time for that person. So min of the two.

    Now check sample 1: n=3, a=[2,3,9]. Compute splits: k=0: T_you=0, T_friend=10^6-2=999998 -> max=999998? But sample output 8, so obviously we need to compute actual numbers. Wait sample 1 output is 8, not huge. So my reasoning must be wrong? Let's recalc sample 1: positions 2,3,9. You at 1, friend at 10^6. The sample says "you take all the prizes: take the first at 1, the second at 2 and the third at 8". That means you collect all three. You start at 1, you need to get to 9? Actually you take first at 1? They say take the first at 1, but first prize is at position 2. Probably they mean: you start at 1, you pick prize at 2 after 1 second, then at 3 after another second, then at 9 after more seconds? Let's see: you at 1, to get to 2 takes 1 sec, pick it; then to 3 takes 1 sec, pick it; then to 9 takes 6 sec (from 3 to 9 is 6). So total 1+1+6=8 sec. That's what they output. So you collected all three. According to my split approach, if you take all (k=3), T_you = a_n - 1 = 9 - 1 = 8, T_friend = 0, so max = 8. That matches. But why would k=0 give huge time? That would be friend collecting all, which would be much larger because friend is far. So the min over k yields 8. So sample 1 consistent.

    Sample 2: n=2, a=[2, 999995]. Compute splits: k=0: max(0, 10^6-2=999998) = 999998. k=1: max(2-1=1, 10^6-999995=5) = max(1,5)=5. k=2: max(999995-1=999994, 0)=999994. Minimum is 5. So answer 5, matches sample.

    Thus approach is correct.

    But note: The constraints say a_i from 2 to 10^6-1, sorted ascending. n up to 1e5. So we can compute in O(n). Just iterate over possible splits.

    However, there is nuance: The split is defined by a threshold between prizes. For k from 0 to n inclusive, compute left_time = (k==0?0: a[k-1] - 1) if using zero-indexed? Be careful: If we use 0-indexed array indices 0..n-1, then k means number of prizes assigned to you. Then left_max_position = a[k-1] if k>0. So left_time = a[k-1] - 1. Right_min_position = a[k] if k < n. So right_time = 10^6 - a[k]. Then answer = min_{k=0..n} max(left_time, right_time).

    We need to compute this efficiently.

    Edge Cases: If n=0? But n>=1 per constraints.

    Now double-check: Could there be a scenario where it's optimal for you to go beyond the farthest prize assigned to you? No.

    Thus answer = min_{k} max( (k>0 ? a[k-1]-1 : 0), (k<n ? 1000000 - a[k] : 0) ).

    We should also consider that you might not need to go exactly to the farthest prize; if you have no prizes, you just stay, time 0.

    Implementation straightforward.

    But wait, is there any possibility of a better strategy where both persons move and maybe one picks up a prize then hands it over? No, they just pick up.

    Thus answer as above.

    Let's test with some custom cases to ensure no oversight.

    Case: n=3, a=[500000, 500001, 500002]. Compute splits: k=0: left=0, right=10^6-500000=500000 -> max=500000. k=1: left=500000-1=499999? Actually a[0]=500000, left=500000-1=499999, right=10^6-500001=499999 -> max=499999. k=2: left=500001-1=500000, right=10^6-500002=499998 -> max=500000. k=3: left=500002-1=500001, right=0 -> max=500001. Min=499999. So answer 499999.

    But is it possible to do better by interleaving? Suppose you take 500000 and 500002, friend takes 500001. Then left_time = max(500000,500002)-1 = 500001, right_time = 10^6 - min(500001) = 499999, max=500001. Worse. So partition optimal.

    Another scenario: n=1, a=[500000]. Then min split: k=0 gives 500000, k=1 gives 499999? Actually 500000-1=499999, 10^6-500000=500000, so min=499999. So answer 499999. That's the closer distance from either start to that point? Actually distance from 1 is 499999, from 10^6 is 500000. So min distance is 499999. That seems correct.

    Now, could there be a scenario where both persons collect some and the total time is less than the max of the two individual times? No, because they act simultaneously; the time when the last prize is collected is the max of their individual completion times.

    Thus answer is as described.

    Now consider scenario where the optimal split yields left_time and right_time not equal but the maximum minimized.

    Now we need to output integer.

    Constraints: a_i sorted ascending, distinct. We'll read them into list.

    Implementation: n = int(input()) a = list(map(int, input().split())) ans = 10**9 # large for k in range(n+1): left = a[k-1]-1 if k>0 else 0 right = 1000000 - a[k] if k<n else 0 ans = min(ans, max(left, right)) print(ans)

    That's O(n). Works.

    But we must ensure that we consider the possibility of both persons having zero time (n=0 not allowed). So fine.

    Now, is there any subtlety about the fact that the friend is at position 10^6 and moving left? They might also consider going to the right? But there are no prizes to the right (since max a_i <= 10^6-1). So no.

    Thus the problem is solved.

    Now I will produce final answer with explanation.

    But the problem statement says "You start at position 1, your friend — at position 10^6". So friend at 10^6. Yes.

    Thus code: read input, compute answer.

    Potential pitfalls: The positions are sorted ascending, but we don't need to verify. Input size up to 1e5, loops fine.

    Now I'll write solution explanation and code.

    However, I realize that there is also possibility of both persons moving and maybe coordinating such that one picks a prize and then moves to help the other? But since they can only pick when they are at the prize, and the prize must be picked by someone, there is no benefit for them to meet or exchange because the total distance traveled by both could be reduced? But the metric is time, not total distance. They operate in parallel, so the total time is determined by the longer individual time. If one person finishes early, they could theoretically go to help the other by picking some of the other's prizes? But that would require them to move to those prizes, which would add to their own time and possibly reduce the other's time if they reallocate. However, the assignment of who picks which prize is decided beforehand? The problem says: "Now you may discuss your strategy with your friend and decide who will pick up each prize." It doesn't say that they cannot change assignment dynamically or that one cannot pick a prize that was originally assigned to the other. In fact, the decision is about who picks up each prize; they can plan it. But the plan could involve one person starting to move, picking some prizes, and then later the other person might pick some that were originally assigned to the first? But essentially, the assignment is a partition, but we can also consider that both might pick prizes along the way, but they start at opposite ends. Could there be a scenario where it's beneficial for both to move towards each other and exchange? For example, the left person picks some left prizes and then continues to the right to pick some rightmost prizes, while the right person picks some right prizes and then goes left, potentially meeting and handing over? But handing over doesn't matter because prize must be picked; once picked it's done. The only thing is that if both move, the time to pick all prizes is the time when the last prize is picked. If both move, they could potentially collect prizes faster by splitting the list not just by a static partition but also by possibly overlapping routes. For instance, they both could head towards the middle, each collecting prizes on their side. But that's essentially the same as a partition where you take left part and friend takes right part. But could there be a scenario where it's beneficial for both to cover some of the same region? For example, consider prizes at positions 2 and 3 (both very left). If you take both, your time = 3-1=2. If you took only one and friend took the other, friend would have to travel from 10^6 to 2, which is huge, so that's worse. So static partition is good.

    But consider prizes at positions 999999 and 999998 (both very right). You would take none, friend takes both, friend time = 10^6-999998 = 2, good. So static partition is fine.

    But what about a more balanced set? The static partition we considered yields the max of the two times. Could we do better by having both move and possibly one pick a prize that is farther from him but the other could pick it later? That would increase the time for the one who picks it, but might reduce the other's time, balancing the max. However, that's essentially captured by the partition because we decide who picks each prize. The only nuance is that the routes could be more complex: For example, suppose we assign a prize to you that is far right, but you could pick it on your way back after meeting friend? But you start at left and move right; you could go all the way to the far right and then maybe turn around to help friend? That would increase your time beyond the farthest prize you picked. So not beneficial.

    But perhaps there is a scenario where both persons move, and one picks a prize that is on the other's side early because they cross? For instance, you both start moving towards each other. You could meet at some point and exchange the responsibility? But picking a prize requires being at its location. If both move, they could coordinate such that each picks prizes in a certain order, possibly overlapping in time. The total time is the time when the last prize is collected. Could we reduce the max by having both persons move towards the middle, each picking prizes as they go, and then maybe one person goes beyond the meeting point to pick some prizes that are on the other side? That would increase that person's time. But maybe by doing so, the other person's time is reduced more, so the max reduces.

    Consider an example: n=2, positions: 400 and 600. According to split method: possible splits: k=0: you 0, friend 10^6-400=999600? Wait 10^6 - 400 = 999600? That's huge, but that's 1e6-400 = 999600? Actually 10^6 = 1,000,000, so 1,000,000-400=999,600. So max=999,600. k=1: you 400-1=399, friend 1,000,000-600=999,400 => max=999,400? That's still huge. Wait compute correctly: 1,000,000-600 = 999,400. So max around 999,400. k=2: you 600-1=599, friend 0 => max=599.

    So best is 599 when you take both. That seems plausible: you go from 1 to 600, taking 599 seconds, picking both along the way; friend does nothing. So answer 599.

    But could we do better by having friend pick the 400 while you pick the 600? That would give times: you 599, friend 999,600? Actually friend picking 400: time = 1,000,000-400 = 999,600, so max huge. So not better.

    What if you pick 400 and friend picks 600? You 399, friend 999,400, max huge. So no.

    Thus partition yields 599.

    But maybe there is a strategy where you both start moving, you go to 600, friend goes to 400. Friend would take 999,600 seconds? Wait friend from 10^6 to 400 requires moving left 999,600 steps, that's huge. So that's worse.

    Thus partition is optimal.

    But what about the scenario where there are many prizes spread across the line, and both persons can move such that they both collect some and then perhaps the faster one helps the slower one? However, since they start at extremes, the slowest time is always determined by the farthest prize from the start for the person who collects it. To reduce the max, we want to assign each prize to the closer person. That's essentially the partition: assign left prizes to you, right prizes to friend. But the "closer" notion is based on distance from start: a prize at position x is closer to you if x-1 < 10^6-x, i.e., x < 500000.5. So the natural split would be around the midpoint. But due to discrete nature, the optimal split might be around that midpoint. That's consistent with our split method.

    But is it always optimal to assign all prizes left of some split to you and all right to friend? Could there be a scenario where both persons collect some prizes that are on the opposite side (i.e., you go to rightmost, friend goes to leftmost) such that they meet and exchange? That seems like a waste because they'd cross each other's paths, but the total time might be lower if they share the load more evenly? Let's think: Suppose we have two prizes: one at position 1? Actually positions start at 2. But imagine positions: 2 and 999999. According to split: k=0 gives 999998? Actually friend time=1e6-2=999998, max=999998; k=2 gives you time=999999-1=999998, max=999998; k=1 gives you time=2-1=1, friend time=1e6-999999=1, max=1. That's best: you take 2, friend takes 999999. So that's partition. So both picking the closer one.

    Now consider three prizes: 400, 500, 600. Split: k=0: friend time=1e6-400=999600. k=1: you=399, friend=1e6-500=999500, max=999500? Actually max(399,999500)=999500. k=2: you=500-1=499, friend=1e6-600=999400, max=999400. k=3: you=600-1=599, friend=0, max=599. So best is 599, you take all three. That's because friend is too far to be useful. So you take all.

    Now consider prizes: 400000, 600000, 800000. Split: k=0: friend time=1e6-400000=600000. k=1: you=400000-1=399999, friend=1e6-600000=400000, max=400000? Actually max(399999,400000)=400000. k=2: you=600000-1=599999, friend=1e6-800000=200000, max=599999. k=3: you=800000-1=799999, max=799999. So best is 400000 at k=1. So assign 400000 to you, 600000 and 800000 to friend. Friend time = 1e6-600000=400000, you time=399999, so max=400000. Could there be a better assignment? Suppose you take 400000 and 800000, friend takes 600000. Then you time=800000-1=799999, friend time=1e6-600000=400000, max=799999. Worse. You take 600000 and 800000, friend takes 400000: you time=800000-1=799999, friend=1e6-400000=600000, max=799999. So best is split at k=1.

    Now consider more nuanced: Suppose we have many prizes close to the center, and we might want to split them such that both persons take some near the center to balance times. That's still a partition of sorted list.

    Thus the split method is optimal.

    Now, is there any possibility of both persons moving and meeting, and then one person gives his collected prizes to the other? That doesn't affect time because once collected, it's done.

    Therefore, answer is as above.

    Now, one more subtlety: The problem says "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." So picking is instantaneous. So time is travel time only.

    Thus we are done.

    Now, we could also compute the answer by considering each prize as a potential split point. The answer is min over i from 0 to n of max( (a[i-1] - 1 if i>0 else 0) , (1000000 - a[i] if i<n else 0) ). That is O(n). We'll implement.

    Edge: a list index: a[-1]? Not allowed. So we handle with condition.

    Now I'll produce final answer.

    But wait, I think we should double-check for the possibility that one person might not go directly to the farthest assigned prize, but could go beyond to reduce friend's time? No, because friend's time depends on his own farthest left. There's no interaction.

    Thus final.

    But before finalizing, let's see if there is any scenario where it's beneficial for you to go beyond your farthest prize to help friend? Suppose you both start moving towards each other. Could there be a scenario where you go beyond the split point to collect a prize that would otherwise be collected by friend, thereby reducing friend's max distance? But then you'd have to travel further, increasing your time. Since the total time is the max, we need to compare. Suppose we have a split that yields times T_you and T_friend. If you take an extra prize that is further to the right beyond your current farthest, your T_you increases. If that prize was originally assigned to friend, then friend's T_friend might decrease if that prize was his leftmost (i.e., the smallest in his set). So it could be beneficial if the increase in your time is less than the decrease in friend's time, and the max reduces. But that is exactly captured by adjusting the split point. Because taking an extra prize from the friend's set corresponds to moving the split point to the right. So we can consider moving the split incrementally. The optimal split is the one that minimizes max(T_you, T_friend). So our enumeration over all splits covers all possibilities.

    Thus solution is correct.

    Now, the answer can be up to 10^6? Actually max time can be up to 10^6-2? Since a_i up to 999999, min distance from either start could be up to 999998 (if a_i=2, friend distance = 999998). So answer fits within int.

    Implementation details: Use constants: MAX_POS = 10**6.

    Now produce Python code.

    But let's also think about O(n) loop: n up to 100000, fine.

    Potential optimization: Could also use binary search, but not needed.

    Now, confirm with sample 1: a=[2,3,9], compute: k=0: left=0, right=10^6-2=999998 => max=999998 k=1: left=2-1=1, right=10^6-3=999997 => max=999997 k=2: left=3-1=2, right=10^6-9=999991 => max=999991 k=3: left=9-1=8, right=0 => max=8 min=8. Correct.

    Sample2: a=[2,999995], compute: k=0: max(0, 10^6-2=999998)=999998 k=1: left=2-1=1, right=10^6-999995=5 => max=5 k=2: left=999995-1=999994, right=0 => 999994 min=5.

    So works.

    Now final answer.

    I'll write the solution explanation: Reduce to splitting array into prefix for you and suffix for friend, compute times, take min of max.

    Now code.

    Be careful: Input might have extra spaces. Use sys.stdin.

    Implementation:

    def solve(): import sys data = sys.stdin.read().strip().split() if not data: return n = int(data[0]) a = list(map(int, data[1:1+n])) max_pos = 1000000 ans = max_pos # large for k in range(n+1): left_time = a[k-1] - 1 if k > 0 else 0 right_time = max_pos - a[k] if k < n else 0 cur = max(left_time, right_time) if cur < ans: ans = cur print(ans)

    Now test with examples.

    Edge: n=1, a=[2] -> k=0: left=0, right=1000000-2=999998, cur=999998; k=1: left=2-1=1, right=0, cur=1; ans=1. Correct? But distance from 1 to 2 is 1, from 10^6 to 2 is 999998, so min=1. Yes.

    Now, what about n=1, a=999999 -> left=999999-1=999998, right=0 for k=1; k=0: left=0, right=1000000-999999=1; ans=1. That matches min distance from friend =1. Good.

    Now, any nuance about the fact that both start moving at same time and can pick up prizes simultaneously? That's accounted for by taking max.

    Thus solution is correct.

    Now produce final answer with explanation.

    But wait, there is a potential nuance: The friend's time to collect his set is not simply 10^6 - min(S_friend) if his set is nonempty? Because he must collect all his prizes, which are all greater than or equal to min(S_friend). As argued, moving from 10^6 directly to min(S_friend) will pass through all larger positions, so he collects them all. However, what if his set includes some positions that are less than min(S_friend)? That's impossible because min is smallest. So yes.

    But consider if friend's set includes positions both left and right of his start? No, all are <= 10^6-1, so left.

    Thus fine.

    Now, is there any scenario where the friend might go beyond the leftmost prize to also pick up some prizes that are on the far left but then turn back? That would be longer, not needed.

    Thus done.

    Now, we might also note that we could compute ans without loop by two-pointer, but loop is fine.

    One more test: n=100000, all prizes from 2 to 100001? Actually positions up to 10^6-1. But okay.

    Now I'll produce final output.

    But hold on: There's also possibility that the optimal strategy might involve not collecting all prizes by the person who goes to the farthest assigned prize, but maybe both persons could move and meet, and one could hand over prizes? That doesn't reduce time.

    Thus final.

    Now writing final answer.

    However, while the problem seems simple, I recall that some Codeforces problem "Run For Your Prize" had a similar solution. I think the solution is indeed min over splits.

    Let me double-check with some random small cases by brute force enumeration of assignments for n small to verify.

    We can test for n=2: positions a,b with a<b. Possible assignments:

    • both to you: time = b-1.
    • both to friend: time = 10^6 - a.
    • you a, friend b: time = max(a-1, 10^6 - b).
    • you b, friend a: time = max(b-1, 10^6 - a).

    The min of these four options is indeed min( b-1, 10^6-a, max(a-1, 10^6-b), max(b-1, 10^6-a) ). Our split enumeration gives k=0: max(0,10^6-a) = 10^6-a; k=1: max(a-1,10^6-b); k=2: max(b-1,0)=b-1. So we include the three distinct options (the assignment you b, friend a yields max(b-1,10^6-a) which is covered by k=2? Actually k=2 gives b-1, not max(b-1,10^6-a) because friend's set is empty, so time 0. But assignment you b, friend a is not a partition because friend takes a which is left of b. That's not a prefix-suffix split. But is it ever optimal? Let's compare: If we consider you b, friend a: time = max(b-1, 10^6 - a). Compare to other options. Could this be better than the split options? For example, a=400, b=600. Options:

    • both you: 599
    • both friend: 999600
    • you a, friend b: max(399, 999400)=999400
    • you b, friend a: max(599, 999600)=999600 So best is 599 (both you). So not better.

    What about a=2, b=999999:

    • both you: 999998
    • both friend: 999998? 10^6-2=999998
    • you a, friend b: max(1,1)=1? Actually 10^6-999999=1, a-1=1, max=1.
    • you b, friend a: max(999998, 999998)=999998. So best =1. That's covered by split k=1 (you a, friend b) which is a split (prefix of size 1). So indeed you b, friend a is not optimal here.

    But consider a=400000, b=600000:

    • both you: 599999
    • both friend: 600000? Actually 10^6-400000=600000.
    • you a, friend b: max(399999, 400000)=400000
    • you b, friend a: max(599999, 600000)=600000 So best 400000, which is split at k=1.

    What about a=500000, b=500001:

    • both you: 500000? Actually b-1=500000
    • both friend: 10^6-500000=500000
    • you a, friend b: max(499999, 499999)=499999
    • you b, friend a: max(500000, 500000)=500000 Best 499999, split at k=1.

    So split seems to cover the best. The assignment you b, friend a (cross) is never better than the best of split options? Let's try to find a counterexample: we want max(b-1, 10^6-a) < min( max(a-1,10^6-b), a-1? Actually we want cross assignment to beat both split assignments that involve one each? But cross is not a split because it's not prefix-suffix; it's swapping. But it could be better than both split options? Let's denote option1: k=1 (you a, friend b): T1 = max(a-1, 10^6-b). Option2: k=2 (you both): T2 = b-1. Option3: k=0: T0 = 10^6 - a. Cross: T_cross = max(b-1, 10^6-a). Since b-1 >= a-1 (as b > a), and 10^6-a >= 10^6-b, T_cross is at least both T2 and T0? Actually T_cross = max(b-1, 10^6-a). Compare to T2 = b-1 and T0 = 10^6-a. So T_cross = max(T2, T0). Therefore T_cross >= max(T2, T0). So cross is at least as large as both T2 and T0 individually. And T1 = max(a-1, 10^6-b). Could T_cross be less than T1? Possibly if T1 is larger. But since T_cross >= T2 and T0, and we are minimizing, we would pick the smallest among T0, T1, T2. T_cross being >= T0 and T2, it can't be smaller than both. It could be smaller than T1 if T1 is even larger, but we already have T0 and T2 as candidates which are <= T_cross. So the minimum of {T0, T1, T2} is <= T_cross. Thus cross is never better than the best split. So indeed split covers optimum.

    Thus our approach is correct.

    Now finalize answer.

    But wait: There's nuance when n is large and we split such that one set is empty. That's covered by k=0 or k=n.

    Thus final solution.

    Now I'll produce final message with explanation and code.

    Also note: The problem says positions are given in ascending order. So we don't need to sort.

    Now produce final answer. We need to minimize the total time to collect all prizes. Since both participants start at opposite ends and move at the same speed, the total time is the maximum of the times each person needs to finish their assigned prizes.

    For a given assignment, the fastest way for the participant starting at 1 is to simply walk to the rightmost prize they have to collect; they will pass all their prizes on the way. Their time is max(S_you) - 1 (or 0 if they collect nothing).
    Similarly, the friend starting at 10⁶ walks left; their time is 10⁶ - min(S_friend) (or 0).

    An optimal assignment can always be taken as a split of the sorted list: the first k prizes (the smallest positions) are taken by the player at 1, the rest by the friend. Any crossing assignment can be swapped without increasing the total time.

    Thus we just need to try all k from 0 to n and compute
    t1 = a[k-1] - 1 if k>0 else 0,
    t2 = 1_000_000 - a[k] if k<n else 0,
    and take min_k max(t1, t2).

    The answer is the minimal possible total time.

    import sys
    
    def solve() -> None:
        data = sys.stdin.read().strip().split()
        if not data:
            return
        n = int(data[0])
        a = list(map(int, data[1:1 + n]))
    
        MAX_POS = 1_000_000
        ans = MAX_POS
    
        for k in range(n + 1):
            left = a[k - 1] - 1 if k > 0 else 0
            right = MAX_POS - a[k] if k < n else 0
            cur = max(left, right)
            if cur < ans:
                ans = cur
    
        print(ans)
    
    if __name__ == "__main__":
        solve()