Чому корова перейшла дорогу II (Золото)

Фермер Джон розводить $n$ порід корів, яким для зручності присвоєно номери від $1$ до $n$. Деякі пари порід є більш дружніми одна до одної, ніж інші. Цю властивість можна просто визначити за номерами порід: породи $a$ і $b$ є дружніми, якщо |a - b| \le 4, і недружніми в іншому випадку.

Через ферму Фермера Джона проходить довга дорога. На одній стороні дороги розташована послідовність з $n$ полів — по одному полю для кожної породи. На протилежній стороні дороги також розташована послідовність з $n$ полів, по одному для кожної породи. Щоб допомогти коровам безпечно переходити дорогу, Фермер Джон хоче побудувати пішохідні переходи, що з'єднують поля на протилежних сторонах дороги. Перехід можна побудувати тільки між двома полями, номери порід яких є дружніми.

За заданим порядком розташування $n$ полів на кожній стороні дороги допоможіть Фермеру Джону визначити максимальну кількість пішохідних переходів, які він може побудувати так, щоб жодні два переходи не перетиналися.