A1301. [COCI-2013_2014-contest4]#2 GUMA

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 shape.

The first line of input contains the integer N (1 ≤ N ≤ 100 000).
Each of the following N+1 lines contains an integer ai (1 ≤ ai ≤ 100 000), representing the number of parts which the ith vertical section should consist of.

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

In test cases worth 20% of total points, N will not exceed 100.