A factory called Gumi-Gumi is dedicated to making tires. Their carving machine is responsible for carving fillisters into the tire. The tire has $N$ vertical fillisters which divide the rubber into $N+1$ vertical parts. Horizontal cuts are made on each vertical part so that all parts comprising the vertical part are of equal size. The machine can make fillisters on one or more not necessarily continuous vertical sections in one cut, but it can only cut in a straight line.

An example of a tire cutting strategy, corresponding to the third sample test:

The topmost and the lowest lines represent a full horizontal cut, whereas the first and the last vertical lines are the ends of the tire.

You are given the shape of the tire. Your task is to calculate the minimal possible number of cuts necessary in order to obtain such a shape.

Input Specification

The first line of input contains the integer $N$ $(1\le N\le 100000)$.

Each of the following $N+1$ lines contains an integer $a_i$ $(1\le a_i\le 100000)$, representing the number of parts which the $i^{\text{th}}$ vertical section should consist of.

Output Specification

The first and only line of output must consist of the minimal number of cuts required.

Scoring

In test cases worth $20\mathrm{\%}$ of total points, $N$ will not exceed $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