\(4^{th}\) round, January \(18^{th}\), 2014

A factory called Gu\(mi-Gu\)mi 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.

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

\(4^{th}\) round, January \(18^{th}\), 2014

The first line of input 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\)), representing the number of
parts which the i^{th} vertical section should consist of.

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

생성자가 기록되지 않았습니다.

출처 COCI 2013/2014 Contest 4