Problem Description

Given a rectangle with \( N+1 \) columns, the \( i \)-th column must be horizontally cut \( A_i-1 \) times to be divided into \( A_i \) equal parts. Calculate the minimum number of cuts required to complete the division as specified.

Tips: A single cut can be performed on one or multiple, possibly non-consecutive, columns.

Input Format

The first line contains a positive integer \( N \), representing the number of columns in the rectangle minus one.

The next \( N+1 \) lines each contain a positive integer \( A_i \), indicating that the \( i \)-th column must be horizontally cut \( A_i-1 \) times to be divided into \( A_i \) parts.

Output Format

A single line containing a positive integer, representing the minimum number of cuts required.

Sample Input and Output

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

Notes

[Sample Explanation #3]

A total of 7 cuts are required.

[Data Range]

For 20% of the data, \( 1 \le N \le 100 \).

For 100% of the data, \( 1 \le N, A_i \le 10^5 \).

[Source]

This problem is scored according to the original COCI settings, with a maximum score of 120.

Translated from COCI2013-2014 CONTEST #4 T4 GUMA.

见题面 Input 部分

见题面 Output 部分