Observatory Antenna Prime Cadence

MediumArrayMathNumber theoryPrimesSieveBinary search2 sample tests6 hidden tests

A radio observatory maintains a straight row of n antennas, each currently tuned to an integer frequency measured in MHz. Observatory policy requires the row to follow one consistent alternating cadence from end to end: either every antenna at an even position (0-indexed) is tuned to a prime frequency while every antenna at an odd position is tuned to a non-prime frequency, or the reverse — every even position non-prime and every odd position prime. The chief engineer may pick whichever of the two cadences turns out to be cheaper to reach.

Any antenna may be retuned any number of times; each retuning operation shifts that antenna's frequency by exactly 1 MHz, up or down, and costs 1 unit of effort. A frequency may never be retuned down to 0 or below — it must always remain a positive integer. A frequency f counts as prime only when f is at least 2 and has no positive divisors besides 1 and f; a frequency of 1, or any composite number, counts as non-prime.

Determine the minimum total number of retuning operations needed to bring the whole row into a valid alternating cadence, taking the cheaper of the two possible cadences.

Input format

Line 1: a single integer n, the number of antennas.
Line 2: n space-separated integers a_1 ... a_n, the current frequency of each antenna in row order.

Output format

A single integer: the minimum total number of unit retuning operations needed to reach a valid alternating cadence (the smaller of the two possible cadences' costs).

Constraints

2 <= n <= 2 * 10^5
1 <= a_i <= 10^6

Examples

Example 1

Input

4
2 3 5 4

Expected

Explanation

Cadence A (even positions prime, odd positions non-prime): position 0 (value 2) is already prime, cost 0; position 1 (value 3) must become non-prime, and the nearest non-prime is 4, cost 1; position 2 (value 5) is already prime, cost 0; position 3 (value 4) is already non-prime, cost 0. Cadence A total = 1. Cadence B (the reverse) works out to a total of 3. The cheaper cadence gives 1.

Example 2

Input

3
10 10 10

Expected

Explanation

Cadence A (even positions prime, odd positions non-prime): positions 0 and 2 (value 10) each need the nearest prime, which is 11, costing 1 each; position 1 (value 10) is already non-prime, cost 0. Cadence A total = 2. Cadence B (even positions non-prime, odd positions prime): positions 0 and 2 are already non-prime, cost 0 each; position 1 needs the nearest prime, 11, costing 1. Cadence B total = 1. The cheaper cadence gives 1.

Ready to solve this?