Run For Your Prize

당신과 친구는 TV 쇼 "Run For Your Prize"에 참가하고 있다.

쇼가 시작될 때 n개의 상품이 직선 위에 놓여 있다. i-th번째 상품은 위치 ai에 있다. 모든 상품의 위치는 서로 다르다. 당신은 위치 1에서, 친구는 위치 106에서 시작한다(이 두 위치에는 모두 상품이 없다). 당신과 친구는 한 팀으로 협력하여 임의의 순서로 모든 상품을 가능한 최소 시간에 수집해야 한다.

당신과 친구 모두 위치 x에서 위치 x + 1 또는 x - 1로 이동하는 데 정확히 1초가 걸린다. 또한 충분히 훈련했기 때문에 상품의 위치가 현재 위치와 같으면 즉시 그 상품을 집을 수 있다(친구도 마찬가지이다). 상품을 운반하는 것은 당신의 속도(또는 친구의 속도)에 전혀 영향을 주지 않는다.

이제 친구와 전략을 논의하고 각 상품을 누가 집을지 정할 수 있다. 모든 상품은 당신이나 친구 중 한 명이 반드시 집어야 한다는 것을 기억하라.

모든 상품을 집는 데 걸리는 최소 시간은 몇 초인가?

첫 번째 줄에 상품의 수를 나타내는 정수 하나 n (1 ≤ n ≤ 105)이 주어진다.

두 번째 줄에 상품의 위치를 나타내는 n개의 정수 a1, a2, ..., an (2 ≤ ai ≤ 106 - 1)이 주어진다. 같은 위치에 놓인 두 상품은 없다. 위치는 오름차순으로 주어진다.

모든 상품을 수집하는 데 걸리는 최소 시간을 초 단위의 정수 하나로 출력한다.

첫 번째 예제에서는 당신이 모든 상품을 가져간다. 첫 번째 상품은 1에서, 두 번째 상품은 2에서, 세 번째 상품은 8에서 가져간다.

두 번째 예제에서는 당신이 첫 번째 상품을 1초 만에 가져가고 친구가 다른 상품을 5초 만에 가져간다. 이를 동시에 수행하므로 총시간은 5이다.