Problem Description

Given a rectangle with $N + 1$ columns, the $i$-th column must be evenly divided into $A_i$ parts by making $A_i - 1$ horizontal cuts. Find the minimum number of cuts needed to finish the partition as required.

$Tips:$ In one cut, you may cut in one or more columns that are not necessarily consecutive.

Input Format

The first line contains a positive integer $N$, indicating that the rectangle has $N + 1$ columns.

The next $N + 1$ lines each contain a positive integer $A_i$, indicating that the $i$-th column must be evenly divided into $A_i$ parts by making $A_i - 1$ horizontal cuts.

Output Format

One line containing a positive integer, indicating the minimum number of cuts.

1
2
5

5

2
3
7
14

15

9
4
2
4
1
2
2
2
8
4
2 

7

Hint

[Sample Explanation #3]

A total of $7$ cuts.

[Constraints]

For $20\%$ of the testdata, $1 \le N \le 100$.

For $100\%$ of the testdata, $1 \le N, A_i \le 10^5$.

[Source]

The score of this problem is set according to the original COCI problem, with a full score of $120$.

Translated from COCI2013-2014 CONTEST #4 T4 GUMA.

Translated by ChatGPT 5