IMO олимпиада по математике 1999 года | Казахстанские олимпиады

В квадрате клетчатой бумаги размером $n\times n$ клеток, где $n$ — четное число, отмечены $N$ клеток таким образом, что каждая клетка квадрата (отмеченная или неотмеченная) имеет хотя бы одну отмеченную соседнюю клетку. (Соседними считаются клетки, имеющие общую сторону.) Определите наименьшее возможное значение $N$.