9667번 - 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 a_i (1 ≤ a_i ≤ 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.

제한

힌트