Một nhà máy tên là Gumi-Gumi chuyên sản xuất lốp xe. Máy khắc của họ chịu trách nhiệm khắc các chất độn vào lốp xe. Lốp có N miếng đệm dọc chia cao su thành N+1 phần thẳng đứng. Các vết cắt ngang được thực hiện trên từng phần thẳng đứng sao cho tất cả các phần tạo thành phần thẳng đứng có kích thước bằng nhau. Máy có thể tạo các miếng đệm trên một hoặc nhiều phần không nhất thiết phải liên tục theo chiều dọc trong một lần cắt mà chỉ có thể cắt theo đường thẳng.

Một ví dụ về chiến lược cắt lốp, tương ứng với mẫu thử nghiệm thứ ba.

Các đường trên cùng và dưới cùng thể hiện một đường cắt ngang hoàn toàn, trong khi các đường thẳng đứng đầu tiên và cuối cùng là phần cuối của lốp.

Bạn được cung cấp hình dạng của lốp xe. Nhiệm vụ của bạn là tính toán số lần cắt tối thiểu cần thiết để có được hình dạng như vậy.

Input

• Dòng đầu tiên chứa số nguyên ~N~ ~(1 ≤ N \le 100 000)~.
• Mỗi dòng trong số ~N+1~ dòng tiếp theo chứa một số nguyên ~a_i~ ~(1 ≤ ai ≤ 100 000)~, biểu thị số phần mà phần dọc thứ ~i~ phải bao gồm.

Output

• Dòng đầu tiên và duy nhất của đầu ra phải bao gồm số lần cắt tối thiểu được yêu cầu.

Scoring

• Trong các ca kiểm thử chiếm 20% tổng số điểm, ~N~ sẽ không vượt quá 100.

Sample Input 1

1
2
5

Sample Output 1

5

Sample Input 2

2
3
7
14

Sample Output 2

15

Sample Input 3

9
4
2
4
1
2
2
2
8
4
2

Sample Output 3

7