Международная олимпиада 2022, Осло, Норвегия, 2022 год

Пусть $n$ — целое положительное число. Нордическим квадратом будем называть любую таблицу $n \times n$, клетки которой заполнены числами от 1 до $n^2$ так, что каждое число использовано по одному разу и в каждой клетке записано ровно одно число. Две клетки назовем соседними, если у них есть общая сторона. Долиной назовем любую клетку, такую что во всех соседних с ней клетках записаны числа, большие чем в ней. Подъемом назовем последовательность, состоящую из не менее чем одной клетки, такую что
   1. первая клетка в последовательности — долина;
   2. каждая следующая клетка последовательности является соседней с предыдущей;
   3. числа, записанные в клетках последовательности, расположены в порядке возрастания.
   Для каждого заданного $n$ найдите наименьшее возможное количество всем подъемов в нордическом квадрате.

Комментарий/решение