Ở giữa đêm, một nhóm du khách muốn qua một cây cầu cũ và đổ nát. Họ đã chỉ có một chiếc đèn pin, ánh sáng của đèn pin chỉ cho phép nhiều nhất hai khách du lịch qua cầu cùng một lúc. Các du khách không thể qua cầu mà không có đèn pin hoặc trong các nhóm lớn hơn hai trừ khi họ muốn rơi xuống sông. Mỗi du khách cần một lượng thời gian nhất định để vượt qua cây cầu. Hai khách du lịch qua cầu với nhau cần một khoảng thời gian của người chậm nhất trong nhóm hai người qua cầu.

Cho n là số người trong đoàn du khách, người thứ i có thời gian qua cầu là a[i].

Yêu cầu: Tìm thời gian ngắn nhất để đoàn du khách qua cây cầu.

Dữ liệu vào:

• Dòng đầu chứa số nguyên dương n là số người trong đoàn khách du lịch (1 ≤ n ≤ 100000);

• Dòng thứ i trong n dòng tiếp theo, mỗi dòng ghi một số nguyên dương a[i] là thời gian để du khách thứ i qua cầu. Tổng thời gian qua cầu của n du khách không vượt quá 10^9.

Dữ liệu ra:

Gồm một số duy nhất là thời gian ngắn nhất để đoàn du khách qua cầu.

Sample Input

4
6
7
10
15

Sample Output

42