D. Үнээнүүд ба гоё дараалал

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Бесси болон үнээнүүд "гоё" дарааллыг бүтээх гэж оролдож байлаа. Харамсалтай нь тэд арифметикдээ тааруу учраас тэдэнд чиний тусламж хэрэгтэй байна.

Хэрвээ $х$ нь дараалсан $y$ бүхэл тооны (заавал эерэг байх албагүй) нийлбэрээр илэрхийлэгдэх бол эерэг бүхэл тооны ($x, y$) хос нь "гоё" болно. Хэрвээ ($a_1, a_2$), ($a_2, a_3$), ... , ($a_{n-1},a_n$) хосууд бүгд "гоё" бол ($a_1, a_2, ... , a_n$) дараалал "гоё" болно.

Үнээнүүдэд $n$ эерэг бүхэл тоон $a_1, a_2, ... , a_n$ дараалал байв. Нэг үйлдлээр $a_i$-г бусад эерэг бүхэл тоогоор сольж болно (шинэ $a_i$-н утганд ямар нэг хязгаар байхгүй). Дарааллыг гоё болгоход шаардагдах хамгийн бага үйлдлийн тоог ол.

Оролт

Эхний мөр нэг бүхэл тоо $n$ ($2 ≤ n ≤ 5000$) өгөгдөнө. Дараагийн мөр $a_1, a_2, ... , a_n$ ($1 ≤ a_i ≤ 10^{15}$) бүхэл тоонуудыг агуулна.

C++ хэл дээр 64-битийн тоо хэрэглэх үед %lld-г хэрэглэхгүй байхыг зөвлөж байна. %I64d, эсвэл cin, cout стриймийг ашиглана уу.

Гаралт

Дарааллыг гоё болгож өөрчлөх нийт $a_i$ өөрчлөлтийн хамгийн бага утга болох ганц тоог хэвлэ.

Орчуулсан: Батхишиг

Жишээ тэстүүд

Оролт
3
6 4 1
Гаралт
0
Оролт
4
20 6 3 4
Гаралт
2

Тэмдэглэл

In the first sample, the sequence is already cool, so we don't need to change any elements. In the second sample, we can change $a_{2}$ to 5 and $a_{3}$ to 10 to make (20, 5, 10, 4) which is cool. This changes 2 elements.

Сэтгэгдлүүдийг ачааллаж байна...