Minimizing Maximum Elevation Path

You are given a square terrain represented by an N×N grid where each cell has an elevation. Your task is to find a path from any cell in the leftmost column to any cell in the rightmost column such that the maximum elevation encountered along the path is minimized.

The path may move horizontally, vertically, or diagonally. Formally, if you traverse cells with elevations (e_1, e_2, \ldots, e_k) along a path, your goal is to minimize (\max(e_1, e_2, \ldots, e_k)).

Input Constraints:

• 2 \(\le N \le 100\)
• The next N lines each contain N integers representing the elevation values.

Example:
For a 3×3 grid:

1 2 3
4 5 6
7 8 9

The best path has a maximum elevation of 3.

inputFormat

The first line contains an integer N, representing the size of the grid. The next N lines each contain N space-separated integers indicating the elevation values in that row.

outputFormat

Output a single integer representing the minimum possible value of the maximum elevation encountered along a valid path.## sample

3
1 2 3
4 5 6
7 8 9

3