Có \(n\) cuốn sách, và Kotivalo và Justiina sẽ đọc tất cả chúng. Đối với mỗi cuốn sách, bạn biết thời gian cần thiết để đọc nó.

Cả hai đều đọc từng cuốn sách từ đầu đến cuối, và họ không thể đọc một cuốn sách cùng một lúc. Tổng thời gian tối thiểu cần thiết là bao nhiêu?

Input

• Dòng đầu vào đầu tiên có một số nguyên \(n\): số lượng cuốn sách.
• Dòng thứ hai có \(n\) số nguyên \(t_1,t_2,\ldots,t_n\): thời gian cần thiết để đọc mỗi cuốn sách.

Output

• In một số nguyên: tổng thời gian tối thiểu.

Constraints

• \(1 \leq n \leq 2 \cdot 10 ^ 5\)
• \(1 \leq t_i \leq 10 ^ 9\)

Example

Sample input

3
2 8 3

Sample output

16