该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

Special for beginners, ^_^

Description

约翰和牛贝茜享受了最有趣的假期，他们花了一整天在山上漫步，最后疲惫地回到他们假日的小屋。

由于爬山需要很多体力，而且他们已经非常疲惫，所以他们想要穿过一条最高点和最低点高差最小的路径回到他们的小屋，尽管这个样的路径或许很长，帮助约翰找到这样一条易于攀登的路线！

Format

Input

第1行输入一个单独的整数N接下来输入NxN的矩阵.

Output

一个整数，表示路径上最高点和最低点的高度差。

Samples

5
1 1 3 6 8
1 2 2 5 5
4 4 0 3 3
8 0 2 3 4
4 3 0 2 1

2

Limitation

1s, 1024KiB for each test case.