Sau khi sản xuất xong một chiếc lốp ô tô. Công đoạn tiếp theo là khắc các rãnh dọc và ngang lên bề mặt lốp để tạo độ ma sát với mặt đường khi ô tô di chuyển. Chiếc lốp đã được khắc \(N\) đường dọc để tạo ra \(N + 1\) múi đều nhau. Mỗi một múi sẽ có một số đường ngang cắt qua chia múi này thành những phần bằng nhau. Xem minh họa hình vẽ dưới đây:

Khi thực hiện các đường cắt ngang. Mỗi lần máy cắt có thể thực hiện đường cắt ở trên nhiều múi khác nhau, tuy nhiên các đường cắt này phải thẳng hàng. Hỏi rằng số lần cắt ngang tối thiểu cần thực hiện.

Input

• Dòng đầu tiên ghi số nguyên dương \(N \le 10^5\) số đường cắt dọc.
• \(N + 1\) dòng tiếp theo, mỗi dòng ghi số nguyên dương \(a_i \le 10^5\) - số phần chia bằng nhau được thực hiện trên múi thứ \(i\).

Output

• Một số nguyên là số lần cắt ngang tối thiểu cần thực hiện.

Example

9
4
2
4
1
2
2
2
8
4
2

7

1
2
5

5