Sonya Clears the Array

Pussycat Sonya has an array A consisting of N integers (N is even). She can perform operations of two types:

• increase the value of some element A_i by 1;
• delete some adjacent elements A_i and A_i + 1 such that they are consecutive prime numbers (A_i is a prime number, and A_i + 1 is the next prime number).

She wants to delete all elements from array A. What is the minimum number of operations that she needs to perform?

Input Specification

The first line of the input contains one even integer N, the number of elements in array A (0 ≤ N ≤ 500). The second line contains N space-separated positive integers, the elements of array A (1 ≤ A_i ≤ 10⁶).

Output Specification

Print the minimum number of operations that Sonya needs to perform.

Note

A prime number is an integer greater than 1 that has no positive divisors other than 1 and itself.

Sample Input

1. 4
2. 1 2 4 3

download as text file

Output for Sample Input

1. 5

download as text file

Sample Explanation

• Increase the 2nd element: {1, 2, 4, 3} → {1, 3, 4, 3}.
• Increase the 3rd element: {1, 3, 4, 3} → {1, 3, 5, 3}.
• Delete the 2nd and 3rd elements: {1, 3, 5, 3} → {1, 3}.
• Increase the 1st element: {1, 3} → {2, 3}.
• Delete the 1st and 2nd elements: {2, 3} → {}.