Run For Your Prize ——python题解

Run For Your Prize ——python题解

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

Output8 Input

2

2 999995

Output5

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.

  简单的来说就是你和你的朋友分别在两个地方，你在这头从1开始，他在那头从十的六次方（1000000）的位置，你们一起去捡东西，算出取完东西后时间最短的结果。

题解： 暴力题解 从两边分别计算，先计算出最小的时间(即你去捡东西的时间，和你朋友捡东西时间的最小值)，在把这个值和上一个值进行比较，取出最大值。

n=int(input()) #输入物品数量

list=[int(num) for num in input().split()] #在列表中保存位置

num=0
for x in list:
    num=max(num,min(x-1,1000000-x))
print(num)