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

Constraints

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

Output

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

Example

3
2 8 3

16