Чому корова перейшла дорогу II (Золото)
Фермер Джон вирощує n порід корів, пронумерованих від 1 до n. Деякі пари порід дружніші за інші, що визначається їхніми номерами: породи a і b вважаються дружніми, якщо |a − b| ≤ 4; в іншому випадку вони не дружні.
Через ферму Джона проходить довга дорога. По обидва боки дороги розташовані послідовності з n полів, по одному для кожної породи. Щоб забезпечити безпечний перехід корів через дорогу, Джон хоче намалювати "зебри" — переходи, що з'єднують поля з дружніми породами по обидва боки дороги.
Вам потрібно визначити максимальну кількість "зебр", які можна намалювати так, щоб вони не перетиналися, враховуючи порядок полів з обох сторін дороги.
Вхідні дані
Перша стрічка містить число n (1 ≤ n ≤ 1000). Наступні n стрічок задають порядок полів за номерами порід вздовж однієї сторони дороги. Кожен номер породи — це ціле число в межах від 1 до n. Останні n стрічок задають порядок полів за номерами порід вздовж іншої сторони дороги. Кожна порода з'являється рівно один раз у кожному порядку.
Вихідні дані
Виведіть максимальну кількість непересічних "дружніх зебр", які Джон може намалювати через дорогу.