Largest Exotic Number

Interview

Time limit1sMemory limit512 MB

Summary

Given an N by N matrix, find the largest value that appears at two distinct cells where one cell is up and to the left of the other, or print -1 if none exists.

Level: Medium5 of 10
Topics: Sorting, Matrix, Greedy, Array
Solved: No attempts yet

Problem

Athanasios: I have an interesting problem to propose for ACM-ICPC INC 2017!
Berdine: What is the problem about?
Athanasios: It involves an exotic algorithm.
Berdine: ... alright, let's hear it!

For readability, the element of a matrix A at the a-th row and b-th column, A**a,b, is written as (a, b). Matrix indices start at 1.

Given a matrix A of size N × N, two elements (a, b) and (c, d) form an exotic pair if all three of these conditions hold:

(a, b) and (c, d) have the same value.
At least one of the following holds: a ≠ c, or b ≠ d.
Both of the following hold: a ≤ c, and b ≤ d.

For example, given the matrix:

3 2 1
5 2 3
4 3 4

There are four exotic pairs in the matrix:

(1, 1) and (2, 3), of value 3;
(1, 1) and (3, 2), of value 3;
(2, 1) and (2, 2), of value 2;
(3, 1) and (3, 3), of value 4.

Among those four exotic pairs, (3, 1) and (3, 3) have the largest value, 4. A number like this is called the largest exotic number.

Your task is to find the largest exotic number for a given matrix, or output -1 if there is no such number.

Input

The first line contains an integer: N (2 ≤ N ≤ 300), the size of the matrix. The following N lines each contain N integers separated by a single space: A**i,j (1 ≤ A**i,j ≤ 100,000) is the matrix element at the i-th row and j-th column, for 1 ≤ i ≤ N and 1 ≤ j ≤ N.

Output

Print the largest exotic number for the given input on one line. Print -1 if there is no such number.

Examples3

Example 1
Input
```
3
3 2 1
5 2 3
4 3 4
```
Expected output
```
4
```
Example 2
Input
```
4
3 2 1 4
4 2 1 4
5 1 2 1
3 1 5 6
```
Expected output
```
5
```
Example 3
Input
```
2
1 2
2 4
```
Expected output
```
-1
```