Programming contests

ECN selejtező programozó csapatverseny, 2017. április 12.

April 12, 2017 10:00 AM – April 12, 2017 3:00 PM

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 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 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 ≤ Ai ≤ 106).

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} → {}.
University of Debrecen; Faculty of Informatics; v. 05/24/2018