Задача H. Длинный спуск (45 баллов)

Автор:А. Кленин   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:32 Мб
Выходной файл:output.txt  

Условие

Рельеф горного массива представлен матрицей размером NxN, с элементами, задающими высоту участков местности. Лыжник желает найти самый длинный спуск, т.е. такую строго убывающую последовательность соседних по вертикали или горизонтали элементов ai1,j1 > ai1,j1 > … > aiL,jL, что значение L (длина последовательности)  — максимально возможное.

Формат входного файла

Входной файл содержит число N, за которыми следует N2 чисел a1,1 a1,2a1,N a2,1 a2,2a2,NaN,N. Все числа — целые.

Формат выходного файла

Выходной файл должен содержать искомую максимальную последовательность элементов. Если существует несколько максимальных последовательностей, следует вывести любую из них.

Ограничения

1 ≤ N ≤ 1000, 0 ≤ ai,j ≤ 106.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
4
1 1 1 1
1 1 1 1
1 3 7 1
9 1 8 1
8 7 3 1

0.034s 0.008s 15