Chạy đua nhận thưởng

Bạn và một người bạn cùng tham gia một trò chơi thu thập phần thưởng. Có $n$ phần thưởng nằm trên một đường thẳng, phần thưởng thứ $i$ ở vị trí $a_i$. Các vị trí đều phân biệt.

Bạn xuất phát tại vị trí $1$, người bạn xuất phát tại vị trí ${10}^6$ (không có phần thưởng nào nằm ở hai vị trí này). Mỗi giây, mỗi người có thể di chuyển từ vị trí $x$ sang $x+1$ hoặc $x-1$. Khi một người đang đứng đúng tại vị trí của một phần thưởng thì nhặt được nó ngay lập tức. Việc mang phần thưởng không làm chậm tốc độ di chuyển.

Hai người di chuyển đồng thời và cùng lúc. Hãy phân công ai nhặt phần thưởng nào sao cho tổng thời gian để thu thập hết tất cả phần thưởng là nhỏ nhất. Thời gian tính là thời điểm mà cả hai người đã hoàn thành phần việc của mình.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên $n$, số lượng phần thưởng.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$, các vị trí của phần thưởng, cho theo thứ tự tăng dần. Không có hai phần thưởng nào cùng vị trí.

Dữ liệu ra

• In ra một số nguyên là số giây nhỏ nhất cần để thu thập hết tất cả phần thưởng.

Ràng buộc

• $1\le n\le {10}^5$
• $2\le a_i\le {10}^6-1$

Ví dụ