Em cần phải điều khiển C-Bot vượt qua một đường đua có \(n\) cánh cổng thời gian, được đánh số từ \(1\) đến \(n\).

Khi hiệu lệnh "Bắt đầu!" vang lên, đó là thời điểm \(0\) giây, C-Bot đang đứng ngay trước cánh cổng số \(1\), nhưng các cánh cổng có thể chưa được mở ra.

Cánh cổng thứ \(i\) sẽ mở ra lần đầu tiên sau đúng \(a_i\) giây và tồn tại trong một khoảnh khắc đủ để "dịch chuyển tức thì" rồi đóng và lặp lại như vậy sau \(a_i\) giây tiếp theo (tức là cổng \(i\) mở tại các thời điểm \(a_i, 2 \cdot a_i, 3 \cdot a_i, \dots\)). Ngay khi một cánh cổng xuất hiện trước mặt, C-Bot sẽ được tự động dịch chuyển đến trước cánh cổng kế tiếp mà không mất thêm thời gian. Nếu C-Bot đến trước một cánh cổng nhưng cổng đó chưa mở thì phải chờ ở đó.

Yêu cầu: Hãy tính thời điểm sớm nhất (bằng giây) mà C-Bot được dịch chuyển qua khỏi cánh cổng thứ \(n\) để về đích.

Input

• Dòng đầu tiên chứa số nguyên \(n\) (\(1 \le n \le 10^{10}\)).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 10^9, 1 \le i \le n\)), các số cách nhau một khoảng trắng.

Output

• Dòng đầu tiên ghi số nguyên duy nhất là thời điểm C-Bot hoàn thành thử thách.

Example

4
3 2 3 4

8

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \le 100, a_i \le 10^3\).
• Subtask \(2\) (\(40\%\) số điểm): \(n \le 5 \cdot 10^3\).
• Subtask \(3\) (\(30\%\) số điểm): Không có ràng buộc gì thêm.