Minimum Cost to Achieve Pairwise Coprime Neighbors

Given a sequence of n positive integers. You are allowed to perform the following operation any number of times: choose two adjacent numbers in the sequence, and select a common divisor d > 1 of both numbers, then divide both numbers by d. The cost of this operation is equal to d. Note that you may choose different divisors for different operations.

The goal is to transform the sequence so that every pair of adjacent numbers becomes coprime (i.e. they have a greatest common divisor equal to 1). Compute the minimum total cost required to achieve this.

Note: It is guaranteed that it is always possible to achieve the goal by applying the operations a finite number of times.

Hint: A greedy simulation which repeatedly applies an operation on any adjacent pair whose gcd is greater than 1 is sufficient.

inputFormat

The first line contains an integer n (the number of elements in the sequence).

The second line contains n positive integers separated by spaces.

Note: n will be at least 1. When n = 1, the sequence is already valid.

outputFormat

Output a single integer — the minimum total cost required to transform the sequence so that every adjacent pair of numbers is coprime.

sample

2
4 6

2