Problems
Шахматных дел мастера
Шахматных дел мастера
...И он подошел ко дворцу и увидел, что ворота его
открыты, и, войдя в ворота, он увидел в проходе каменную скамью, а
на скамье -- двух девушек, подобных луне, перед которыми стояла
шахматная доска, и они играли.
"Тысяча и одна ночь", "Сказка о Хасане басрийском"
\includegraphics{https://static.e-olymp.com/content/28/2878f14dbb4d79d7919543bcc64d77bbdc02a384.jpg}
Рассказывают также, что был в древние времена и минувшие века и столетия повелителя правоверных Харун ар-Рашид узнал о такой игре как шахматы. И повелел он тогда плотникам вырезать доску и фигуры, красильщикам -- покрасить их в белый и красный цвет, и лакировщикам - покрыть их лаком.
И сделали они так, и принесли затем доску повелителю. Однако клетки доски были окрашены совсем не в шахматном порядке. Тогда потребовал Харун ар-Рашид объяснения от красильщика. И говорил мастер такое, что на шахматной доске, какой квадрат из клеток ни возьми (со сторонами параллельными сторонам доски), в нем обязательно количество красных и белых клеток будет отличаться друг от друга не больше, чем на \textbf{1}. На той доске, которую он сделал, не обязательно все квадраты будут с таким свойством, но многие.
Заинтересовали повелителя правоверных речи красильщика (хоть и не спасли последнего от казни), и он захотел узнать во скольких различных квадратах на доске, изготовленной красильщиком, разность между количеством красных и белых клеток не более \textbf{1}.
\textbf{Входные даные}
В первой строке задается размер доски \textbf{N (1 ≤ N ≤ 300)}. В последующих \textbf{N} строках записаны по \textbf{N} чисел, каждое из которых определяет цвет соответствующей клетки доски (\textbf{0} - белая, \textbf{1} - красная).
\textbf{Выходные даные}
В единственной строке выведите количество квадратов доски с указанным свойством.
Input example #1
3 1 0 1 0 1 0 1 0 1
Output example #1
14