После пожара 1812 года на одной из главных улиц Москвы уцелел лишь один дом. Вернувшиеся после победы жители решили вновь поселиться на этой улице. При этом каждый решил построить себе дом такой же высоты, каким он был у него до пожара.

Дома будут строиться вплотную друг другу, а крыши соседних домов будут соединяться лестницами (длина лестницы равна разнице высот домов), чтобы трубочист мог путешествовать по крышам и чистить трубы.

Когда план постройки домов был уже почти утвержден, свое веское слово сказал Главный Трубочист. Он попросил построить дома так, чтобы суммарная длина лестниц была минимальной. Помогите ему составить такой план постройки домов.

Рассмотрим целочисленную решетку размера N × N. Пусть некоторые ее узлы покрашены в белый, а некоторые – в черный цвет. Требуется определить количество квадратов на заданной решетке, то есть квадратов, вершины которых совпадают с узлами заданной решетки и покрашены в одинаковый цвет.

Например, на решетке размера 4 × 4, изображенной на рисунке 1 такой квадрат один, он показан на рисунке 2.

Группа альпинистов покорила много вершин и возвратилась в родной город. Одна из местных газет решила написать статью об их походе. Как выяснилось, в процессе похода альпинисты N раз останавливались на ночлег на той или иной высоте h_i. Поскольку главный редактор газеты настаивает, чтобы название статьи было «Восхождение и спуск», решено было не упоминать о некоторых днях похода, рассказав лишь о 2k+1 дне, причем если статья будет рассказывать о x₁-ом, x₂-ом, …, x_2k+1-ом (x₁ < x₂ < … < x_2k+1)) дне, то должно выполняться условие h_x1 < h_x2 < … < h_xk < h_xk+1 > h_xk+2 > … > h_x2k+1 . Найдите максимальное k, для которого можно соответствующим образом выбрать 2k+1 день.