408979: GYM103401 H Observe
Description
In order to collect geographical information on Mount Wolwz, a team of geographical observers needed to establish four observation points on the mountain. In order to obtain accurate data, the four observation points need to be exactly the four vertices of a square when viewed from the air. The observation algorithm used by the team required at least three of the observation points to be at the same height. And for the last observation point, which is at a different height to the other three, it needs to be at a higher position than the other three.
The top view of Mount Wolwz can be seen as a square with $$$n*n$$$ small square platforms, where each piece has an integer height. The group discussed that the higher the three observation points of the same height, the better the result. So they wanted to find out what the highest of the three observation points at the same height was.
InputThe input contains a total of $$$n + 1$$$ lines
The first line contains an integer $$$n(2 \leq n \leq 300)$$$, representing the length of the side of Mount Wolwz
Next $$$n$$$ lines, th $$$i$$$-th line contains $$$n$$$ integers:$$$h_{i,1},h_{i,2},...,h_{i,j},...,h_{i,n}(1 \leq h_{i,j} \leq 10^{9})$$$, representing the height of each of the small platforms of Mount Wolwz
OutputOne line contains an interger, representing the best height. If suitable observation points cannot be established in Mount Wolwz, output "$$$-1$$$"(without quotes).
ExamplesInput3 1 1 3 1 2 2 3 2 3Output
2Input
3 1 2 1 2 2 2 1 2 1Output
-1Note
In the first example, $$$[(1,1),(1,2),(2,1),(2,2)]$$$ and $$$[(2,2),(3,2),(2,3),(3,3)]$$$ are all suitable observation point combinations.