Oiram đang tham gia nhiệm vụ giải cứu công chúa khỏi tòa lâu đài quái vật. Có tổng cộng ~N~ con quái vật trong lâu đài, Oiram phải đánh bại tất cả chúng để giải cứu công chúa. Quái vật thứ ~i~ ~(1 \le i \le N)~ có chỉ số sức mạnh là ~A_i~.

Oiram là một pháp sư về sấm sét, anh ta sử dụng các tia sét để giảm chỉ số sức mạnh và đánh bại quái vật. Ban đầu, Oiram có tổng cộng ~K~ chỉ số năng lượng. Oiram có thể sử dụng ~1~ đơn vị năng lượng của mình để dùng tia sét nhắm vào tối đa hai con quái vật và giảm chỉ số sức mạnh của mỗi con đi ~1~ đơn vị. Một con quái vật bị đánh bại khi chỉ số sức mạnh của nó giảm về ~0~.

Oiram cần tính toán chỉ số năng lượng tổng cộng ban đầu của mình để chuẩn bị cho nhiệm vụ giải cứu công chúa. Bạn hãy giúp Oiram xác định giá trị ~K~ tối thiểu để anh ấy có thể đánh bại toàn bộ ~N~ con quái vật.

Input

• Dòng đầu tiên chứa số nguyên ~N~ ~(1 \le N \le 10^5)~.
• Dòng thứ hai chứa ~N~ số nguyên ~A_i~ ~(1 \le A_i \le 10^9)~.

Output

• In ra giá trị ~K~ tối thiểu để Oiram có thể đánh bại tất cả quái vật.

Examples

Sample Input

4
1 3 2 3

Sample Output

5

Scoring

• Subtask ~1~ với ~50\%~ số điểm: ~A_i \le 2~ với mọi ~1 \le i \le N~
• Subtask ~2~ với ~50\%~ số điểm: Không có ràng buộc gì thêm

Notes

Trong ví dụ, Oiram có thể lựa chọn chiến thuật như sau với ~K=5~ chỉ số năng lượng:

• Tấn công quái vật ~1~ và ~4~, chỉ số sức mạnh của các quái vật là: ~\{0,3,2,2\}~, quái vật ~1~ bị đánh bại.
• Tấn công quái vật ~2~ và ~3~, chỉ số sức mạnh của các quái vật là: ~\{0,2,1,2\}~.
• Tấn công quái vật ~2~, chỉ số sức mạnh của các quái vật là: ~\{0,1,1,2\}~.
• Tấn công quái vật ~3~ và ~4~, chỉ số sức mạnh của các quái vật là: ~\{0,1,0,1\}~, quái vật ~3~ bị đánh bại.
• Tấn công quái vật ~2~ và ~4~, chỉ số sức mạnh của các quái vật là: ~\{0,0,0,0\}~, quái vật ~2~ và ~4~ bị đánh bại.

Có thể nhận thấy rằng với giá trị ~K~ nhỏ hơn ~5~, Oiram không thể đánh bại tất cả các quái vật.