Increments
TopCoder TCO2019, South America Regional
Time Limit: 0.3s, Memory Limit: 64MiB
Ели има масив с N цели числа A1, A2, ..., AN. Тя може да вземе произволен интервал от последователни елементи на масива (включително един единствен елемент или пък всички елементи) и да увеличи всеки от тях с единица. Сега момичето се чуди колко най-малко операции от този тип са нужни, така че накрая всички числа в масива да са прости?
Вход
На първия ред на стандартния вход ще бъде зададено едно цяло число N - броя числа в масива на Ели. На следващия ред разделени със шпации ще бъдат зададени самите елементи на масива A1, A2, ..., AN.
Изход
На единствен ред на стандартния изход изведете едно цяло число - минималния брой операции от описания тип, които Ели трябва да приложи, така че накрая всички числа в резултатния масив да са прости.
Ограничения
- 1 ≤ N ≤ 100
- 1 ≤ Ai ≤ 1,000,000
| Примерен Вход | Примерен Изход |
|---|---|
| 9 1 8 3 3 5 8 7 2 4 | 5 |
| 3 5 7 11 | 0 |
| 2 4 2 | 1 |
| 20 42 17 13 666 80 1 22 123 55 11 91 42 119 16 207 31 186 10 10 63 | 16 |
В първия пример един начин да постигнем оптималния отговор е да увеличим интервала [0, 5] правейки масива (2, 9, 4, 4, 6, 9, 7, 2, 4), след това [7, 9] постигайки (2, 9, 4, 4, 6, 9, 7, 3, 5) след което [1, 5], правейки масива (2, 10, 5, 5, 7, 10, 7, 3, 5) и накрая [1, 1] и [5, 5] по веднъж, за да направим 10-ките равни на 11, достигайки крайния масив (2, 11, 5, 5, 7, 11, 7, 3, 5). Във втория пример числата вече са прости. В третия е достатъчно да увеличим целия масив веднъж за да постигнем (5, 3).