Mountain Peaks Saddle Value

You are given an island represented as an N × M grid. Each cell has an altitude. Two cells are considered adjacent if the difference of their row indices and the difference of their column indices are both at most 1 (diagonals included). A path is a sequence of cells where every two consecutive cells are adjacent.

A flat region is defined as a maximal set of connected cells having the same altitude. A mountain peak is a flat region such that no cell adjacent (in any of the 8 directions) to any cell in the region has an altitude strictly higher than the flat region’s altitude.

For each mountain peak P with altitude H that can reach some mountain peak with higher altitude, define its saddle value as the maximum, over all paths from P to any mountain peak with altitude greater than H, of the minimum altitude encountered along the path. Note: For a mountain peak that does not have any reachable mountain peak with strictly higher altitude, define its saddle value to be 0.

Your task is to compute the maximum saddle value among all mountain peaks on the island.

Important: If a mountain peak is not the highest (i.e. there is a reachable mountain peak with a higher altitude), then you must determine the best possible route (the one with the maximum possible minimum altitude) to a mountain peak with higher altitude and take that minimum altitude along the route as its saddle value. Otherwise, for the highest peak(s), the saddle value is defined as 0.

inputFormat

The first line contains two integers N and M — the number of rows and columns in the grid. Each of the next N lines contains M integers representing the altitudes of the island.

outputFormat

Output a single integer — the maximum saddle value among all mountain peaks.

sample

3 3
1 2 1
2 3 2
1 2 1

0