Vào năm 3021, lúc này loài người đã sinh sống ở ~n + 1~ hành tinh khác nhau, được đánh số từ ~0~ tới ~n~. Điều đặc biệt là tất cả hành tinh này đều nằm trên một đường thẳng. Hành tinh thứ ~i~ cách hành tinh thứ ~(i-1)~ một khoảng là ~a[i]~ năm ánh sáng.

Bạn là một shipper liên hành tinh, hiện tại bạn đang đứng ở hành tinh ~0~ và cần ship ~n~ gói hàng cho ~n~ hành tinh còn lại. Bạn cần đưa ~n~ gói hàng cho ~n~ hành tinh theo đúng thứ tự từ ~1~ tới ~n~.

Dụng cụ bạn được cung cấp là một con tàu có khả năng thực hiện cú nhảy alpha. Với mỗi lần nhảy, con tàu sẽ dịch chuyển tức thời lên phía trước một khoảng bằng ~1~ năm ánh sáng trong ~1~ giây. Hiện nay, ở mỗi hành tinh (kể cả hành tinh ~0~) đều cung cấp một gói nâng cấp tàu vũ trụ: bạn có thể tăng khoảng cách dịch chuyển của con tàu trong một lần nhảy lên một số nguyên dương bất kỳ (tính theo năm ánh sáng). Lưu ý rằng một khi đã tăng thì bạn sẽ không có thể giảm khoảng cách dịch chuyển xuống. Nếu bạn tăng khoảng cách dịch chuyển quá lớn, điều đó có thể dẫn tới việc bạn nhảy lố khỏi hành tinh tiếp theo cần tới. Bạn cũng không thể dịch chuyển ngược về các hành tinh trước.

Với một chiến thuật tăng tốc hợp lý, hãy tính số giây ít nhất mà bạn cần để có thể giao ~n~ gói hàng cho ~n~ hành tinh.

Input

• Dòng đầu tiên chứa số ~n~ là số hành tinh.
• Dòng tiếp theo chứa ~n~ số là khoảng cách ~a[i]~ giữa các hành tinh.

Output

• Số giây ít nhất để giao ~n~ gói hàng

Sample Input

4
4 2 4 7

Sample Output

5

Subtask

• ~30\%~ số test có ~1 \le n \le 3000~, ~1 \le a[i] \le 3000 \; \forall i \in [1; n]~
• ~70\%~ số test còn lại ~1 \le n \le 100000~, ~1 \le a[i] \le 100000 \; \forall i \in [1; n]~

Note

• Ở hành tinh 0, bạn tăng tốc độ của tàu lên 2. Sau đó nhảy 2 lần để tới hành tinh 1 (khoảng cách 4). Thời gian: 2 giây
• Ở hành tinh 1, bạn giữ nguyên tốc độ, nhảy 1 lần tới hành tinh 2 (khoảng cách 2). Thời gian: 1 giây
• Ở hành tinh 2, bạn tăng tốc độ lên 4. Sau đó nhảy 1 lần để tới hành tinh 3 (khoảng cách 4). Thời gian: 1 giây.
• Ở hành tinh 3, bạn tăng tốc độ lên 7. Sau đó nhảy 1 lần để tới hành tinh 4 (khoảng cách 7). Thời gian: 1 giây.
• Tổng thời gian: ~2 + 1 + 1 + 1 = 5~

Lưu ý rằng ở hành tinh 0 bạn không thể tăng tốc độ lên 4, vì nếu tăng lên 4 thì bạn sẽ không có cách nào để nhảy từ hành tinh 1 tới hành tinh 2 (với khoảng cách là 2).