463. Фруктовая радуга

Не решаласьСредняя

Фуд-стилист и художник Оранж создал картину, используя фрукты разных цветов. Картина создана в виде квадрата N×NN \times N. С помощью нейросети художник сгенерировал палитру из N2N^2 цветов в формате OKLCH и присвоил каждому цвету порядковый номер. Полученная палитра обладает следующим свойством: пара цветов с порядковыми номерами ii, jj считается красивой, если i<ji < j. Путь из фруктов в квадрате считается красивым, если цвета всех соседних пар фруктов красивы, а последний фрукт находится на краю квадрата. В качестве соседей фрукта учитываются только вертикальные и горизонтальные фрукты, но не диагональные.

Необходимо написать программу, которая в заданной случайной расстановке найдёт количество фруктов в самом длинном красивом пути, а также количество таких путей.

Формат ввода

В первой строке вводится число NN (1N100)(1 \le N \le 100) — размер матрицы.

В следующих NN строках находится NN чисел Ai,jA_{i,j} (1Ai,jN2)(1 \le A_{i, j} \le N^2), разделённых пробелом, — порядковые номера цветов фруктов.

Гарантируется, что все порядковые номера различны.

Формат вывода

В ответе выведите два числа через пробел: количество фруктов в самом длинном красивом пути и количество таких путей.

Примечание

В условии из Примера 1 существует 88 красивых путей длины 55:

1 2 4 5 9

1 3 4 5 9

1 2 4 6 9

1 3 4 6 9

1 2 4 6 7

1 3 4 6 7

1 2 4 5 8

1 3 4 5 8

Ограничения

Ограничение времени

1 с

Ограничение памяти

256 МБ

Пример 1

Ввод
3
1 2 7
3 4 6
8 5 9
Вывод
5 8

Пример 2

Ввод
4
4 5 11 14
7 12 13 3
2 10 6 8
1 9 16 15
Вывод
4 3

Пример 3

Ввод
6
36 35 34 33 32 31
17 16 15 14 13 30
18 5 4 3 12 29
19 6 1 2 11 28
20 7 8 9 10 27
21 22 23 24 25 26
Вывод
36 1

Теги

Нужно войти, чтобы отправить решение.Войти