This question was the 3rd amongst the 3 questions in the online Hackwithinfy round 2 on 31st May 2020. This was worth 100 points (of total 225 points).
I was not able to solve this.

Question

You are given an array A consisting of N integers. The number of integers N is even. You can perform the following 2 operations:-

1. Increase the value of some element Ai by 1.
2. 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).

You want to delete all the elements of A. What is the minimum number of operations that must be performed?

Example

Input: A = [1, 2, 4, 3], N = 4

Output: 5

Explanation:
We increase A₂ and A₃ by 1. [2 operations]
A = [1, 3, 5, 3]
Remove A₂ and A₃ as they are consecutive primes [1 operation]
A = [1, 3]
Increase A₁ by 1 [1 operation]
A = [2, 3]
Remove A₁ and A₂ as they are consecutive primes. [1 operation]
Total operations = 5