Longest Consecutive Descending Path in a Grid

You are given a grid representing the heights of buildings in a city. Your task is to find the longest path of consecutively descending building heights in a straight line, where a straight line can be horizontal, vertical, or diagonal. A path is defined by starting from a building and moving step-by-step in one of the four directions (right, down, diagonal down-right, or diagonal down-left), provided that each next building is strictly lower in height than the previous one.

Formally, if you start at cell \( (i, j) \) with height \( h \) and move in a fixed direction \( (\Delta i, \Delta j) \), you can continue as long as the next building's height is strictly less than the current one. If the longest chain (number of buildings in the chain) has a length \( L \) (with \( L \geq 2 \)), then the answer is \( L-1 \) (the number of steps taken). If no such descent exists, the answer is 0.

For example, consider the grid:

5 1 2 3
4 6 1 1
3 1 7 1
2 1 1 8

Starting from the cell with 6 and moving left gives a descending chain of length 4 (6, 4, 3, 2), so the answer is 3. In another grid where every row and column is in increasing order, no valid descending path exists and the answer is 0.

The problem may include formulas written in LaTeX; for instance, if a chain has length \( L \), the answer can be computed as:

[ \text{Answer} = \begin{cases} L-1, & \text{if } L \ge 2 \ 0, & \text{otherwise} \end{cases} ]

</p>

inputFormat

The first line of input contains two integers \( m \) and \( n \) representing the number of rows and columns in the grid, respectively.

This is followed by \( m \) lines. Each of these lines contains \( n \) integers separated by spaces representing the heights of the buildings.

You can assume that \( 1 \le m, n \le 1000 \) and the building heights are non-negative integers.

outputFormat

Output a single integer which is the number of consecutive steps in the longest descending path as defined above.

If no valid descending path exists, output 0.

## sample

4 4
5 1 2 3
4 6 1 1
3 1 7 1
2 1 1 8

3