sonya-clears-the-array-icpc-2

Pussycat Sonya has an array A consisting of N integers (N is even). She can perform operations of two types:
increase value of some element Ai by 1
delete some adjacent elements Ai and Ai+1 such that they are consecutive prime numbers (Ai is a prime number and Ai+1 is the next prime number)

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

Input:
The first line of input contains one even integer N - the number of elements in array A.
The second line contains N space separated positive integers - elements of array A.

Output:
Print the minimal 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.

Constraints:
0 ≤ N ≤ 500
1 ≤ Ai ≤ 10^6

SAMPLE INPUT
4
1 2 4 3

SAMPLE OUTPUT
5

Explanation

increase the 2-nd element {1, 2, 4, 3} => {1, 3, 4, 3}
increase the 3-rd element {1, 3, 4, 3} => {1, 3, 5, 3}
delete the 2-nd and 3-rd elements {1, 3, 5, 3} => {1, 3}
increase the 1-st element {1, 3} => {2, 3}
delete the 1-st and 2-nd elements {2, 3} => { }

Source: hackerearth | Difficulty: EASY
Tags: Number theory

Dynamic programming


Solutions: