During the monsoon, a city is shown as an n x n grid called grid. The number grid[i][j] is the height of that block above the ground. Every height is different, and the heights are exactly 0, 1, ..., n*n - 1.
Rain starts at time 0. At time t, the water level is t everywhere. You can move from a block to a block next to it (up, down, left or right) only when both blocks have a height of at most t. Moving itself takes no time, and you must stay inside the grid.
You start at the top-left block (0, 0). Return the earliest time at which you can reach the bottom-right block (n - 1, n - 1).
Examples
Example 1:
Input: grid = [[0,1],[3,2]]
Output: 2
Explanation: Walk 0, 1, 2. The highest block on this path is 2, so you can arrive at time 2.
Example 2:
Input: grid = [[0,2,3],[1,8,4],[7,6,5]]
Output: 5
Explanation: Go along the top row and then down the right side: 0, 2, 3, 4, 5. The highest block on this path is 5.
Example 3:
Input: grid = [[2,0],[1,3]]
Output: 3
Explanation: You start on a block of height 2, so you must wait until time 2. The goal has height 3, so the answer is 3.