training_2007_10_20 - Длинный спуск (45 баллов)

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

задачи
детали
видимые пробелы
простые формулы
широкий текст
редактор

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

Условие

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

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

Входной файл содержит число N, за которыми следует N² чисел a_1,1 a_1,2 … a_1,N a_2,1 a_2,2 … a_2,N … a_N,N. Все числа — целые.

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

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

Ограничения

1 ≤ N ≤ 1000, 0 ≤ a_i,j ≤ 10⁶.

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

№	Входной файл (`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`