Nhân dịp năm mới, công đoàn nhân viên trường Z muốn đến chúc tết tất cả các thầy cô giáo đã và đang giảng dạy ở trường. Trường và nhà của các thầy cô đều nằm trên đại lộ lớn nhất của thành phố, có thể coi con đường là một đoạn thẳng trên trục số với trường ở tọa độ \(0\). Địa chỉ nhà của mỗi giáo viên được cho bởi một số nguyên (dương hoặc âm).

Có \(2\) xe xuất phát từ trường và lần lượt đi tới nhà các thầy/cô. Mỗi nhà chỉ cần đúng \(1\) xe đến thăm và sau khi xe tới nhà một giáo viên thì thầy/cô đó cũng lên xe cùng đi đến nhà các thầy/cô khác. Theo tinh thần "kính lão đắc thọ" và cũng để đảm bảo sức khỏe cho các thầy/cô, người ta muốn sắp xếp lịch trình của từng xe để mỗi giáo viên chỉ phải đến nhà chúc tết những thầy/cô nhiều tuổi hơn mình (không có hai giáo viên nào bằng tuổi).

(Ví dụ như nếu xe có kế hoạch đến nhà cô X (22 tuổi) và thầy Y (80 tuổi) thì bắt buộc phải tới nhà cô X trước, cho dù trên đường tới nhà cô X có chạy qua nhà thầy Y cũng không vào)

Yêu cầu: Hãy lập lịch trình cho từng xe để tổng độ dài của hai hành trình của hai xe tính đến thời điểm tới nhà thầy/cô cuối cùng là nhỏ nhất.

Input

• Dòng đầu chứa số nguyên dương \(n \leq 10^5\) là số thầy/cô trong trường
• Dòng 2 chứa \(n\) số nguyên có giá trị tuyệt đối không quá \(10^9\) là địa chỉ của \(n\) giáo viên, các địa chỉ được liệt kê theo thứ tự tăng dần của tuổi thầy/cô tương ứng

Output

• Ghi ra một số nguyên duy nhất là độ dài nhỏ nhất của tổng hai hành trình.

Example

5
3 -1 -2 1 6

11