Có n con quái xuất hiện trong thành phố. Để tiêu diệt được một con quái cần tốn a[i] viên đạn đối với con quái thứ i. Nếu bạn tiêu diệt hai con quái gần nhau, ví dụ con quái thứ i và i+1 thì chỉ cần 2 x a[i] viên đạn. Nhiệm vụ của bạn là làm sao tốn tổng số đạn ít nhất để tiêu diện hết đám quái và bảo vệ thành phố

Input

• Dòng đầu tiên gồm số nguyên n ~(2\le n\le 10^6)~, số lượng quái vật trong thành phố.
• n số nguyên dương a[i] ~(1 \le a[i] \le 10^9)~, cách nhau bởi dấu cách, số đạn để tiêu diệt quái vật thứ i

Output

In ra tổng số đạn tối thiểu để tiêu diệt hết quái vật

Sample Input

5
1 3 2 5 4

Sample Output

10

Giới hạn

N/A