Tire Groove Cutting

Time limit1sMemory limit128 MB

Summary

Count the distinct horizontal heights that split each of the N+1 strips into its required number of equal pieces.

Level: Medium6 of 10
Topics: Number theory, Math
Solved: No attempts yet

Problem

The Gumi-Gumi factory makes tires. Its carving machine cuts the grooves into the rubber.

A tire has $N$ vertical grooves, which split the rubber into $N+1$ vertical sections. Horizontal grooves are then carved inside each vertical section so that the section falls apart into pieces of equal size.

In one cut the machine can carve one or more vertical sections at the same time, and those sections do not have to sit next to each other. The machine only cuts along a straight line, so every section carved by the same cut is cut at the same height.

A tire cutting strategy that matches the third example.

In the figure, the topmost and the lowest horizontal lines are the edges that run across the whole tire, and the leftmost and the rightmost vertical lines are the ends of the tire. Those edges and the vertical grooves that are already there do not count as cuts.

You are given the shape of the tire. Compute the smallest number of horizontal cuts needed to obtain that shape.

Input

The first line contains the integer $N$ ( $1 \le N \le 100\,000$ ).

Each of the following $N+1$ lines contains an integer $a_i$ ( $1 \le a_i \le 100\,000$ ), the number of pieces the $i$ th vertical section has to consist of.

Output

Print the smallest number of horizontal cuts required.

Examples3

Example 1
Input
```
1
2
5
```
Expected output
```
5
```
Example 2
Input
```
2
3
7
14
```
Expected output
```
15
```
Example 3
Input
```
9
4
2
4
1
2
2
2
8
4
2
```
Expected output
```
7
```