Minimum Horizontal Cuts

You are given a rectangle that is divided into $N+1$ vertical columns. The i-th column must be horizontally cut $A_i-1$ times in order to divide it into $A_i$ equal pieces. However, a single cutting operation can be performed on one or more columns (not necessarily adjacent) at the same time if the cut position (i.e. the relative height) is exactly the same for those columns. Determine the minimum number of cutting operations required to complete the division as per the requirements.

Note: For column i, the required cut positions are at heights k/A_i (for k = 1, 2, ..., A_i-1). Two cuts in different columns can be combined into one operation if the fractions are equal when reduced to simplest form. In other words, if for some columns the cut positions k/A_i and l/A_j are equivalent, they can be executed in one cut operation.

inputFormat

The input consists of two lines.

• The first line contains an integer m (m = N+1), representing the number of columns.
• The second line contains m space-separated positive integers: A₀, A₁, ..., A_m-1, where each A_i denotes that the i-th column must be divided into A_i equal pieces (thus requiring A_i-1 cuts).

outputFormat

Output a single integer: the minimum number of cutting operations required.

sample

2
2 3

3