Trên đường giải cứu công chúa, Mario gặp một mê cung. Mê cung gồm ~N + 1~ căn phòng xếp nối tiếp nhau theo thứ tự phòng ~1~, phòng ~2~, ~...~, phòng ~N + 1~ và lối ra ở phòng ~N + 1~. Giữa ~N + 1~ căn phòng có ~N~ cánh cửa. Ban đầu tại thời điểm ~0~, Mario ở phòng ~1~, tất cả các cánh cửa đều đóng. Cánh cửa thứ ~i~ sẽ chỉ mở vào các thời điểm chia hết cho ~a_i~ rồi đóng lại ngay lập tức. Do Mario khá nhanh nhẹn nên cậu có thể di chuyển giữa 2 căn phòng và qua các cánh cửa mà không mất chút thời gian nào. Hãy tìm thời điểm sớm nhất mà Long sẽ thoát khỏi mê cung.

Input

• Dòng đầu tiên gồm một số nguyên ~N~ là số lượng cánh cửa có trong mê cung ~(1 \le N \le 1000)~.

• Dòng thứ hai gồm ~N~ số nguyên ~a_i~. Cánh cửa thứ ~i~ sẽ mở ra mỗi ~a_i~ giây.

Output

Một số nguyên là thời điểm sớm nhất mà Long sẽ thoát khỏi mê cung.

Sample Input

4
3
2
3
4

Sample Output

8

Note

Mario sẽ thoát ra khỏi mê cung như sau:

• Mario ở phòng 1 tại thời điểm ~0~, cửa 1 đóng, đợi qua ~3~ giây để cửa 1 mở, đi qua phòng 2.

• Mario ở phòng 2 tại thời điểm ~3~, cửa 2 đóng, đợi qua ~1~ giây để cửa 2 mở, đi qua phòng 3.

• Mario ở phòng 3 tại thời điểm ~4~, cửa 3 đóng, đợi qua ~2~ giây để cửa 3 mở, đi qua phòng 4.

• Mario ở phòng 4 tại thời điểm ~6~, cửa 4 đóng, đợi qua ~2~ giây để cửa 4 mở, đi qua phòng 5, và thoát ra mê cung.

Vì tổng thời gian ít nhất cần để thoát mê cung là ~8~ giây, nên in ra ~8~.