Description

Michael likes skiing. This is not surprising, because skiing is really exciting. But to gain speed, the area must slope downward, and when you reach the bottom of the slope, you have to walk back up or wait for a lift to take you. Michael wants to know the longest downhill run in an area. The area is given by a 2D array. Each number represents the elevation of a point. Here is an example:

1   2   3   4   5
16  17  18  19  6
15  24  25  20  7
14  23  22  21  8
13  12  11  10  9

A person can move from a point to one of its four adjacent points (up, down, left, or right) if and only if the elevation decreases. In the example above, one possible run is $24-17-16-1$ (starting at $24$ and ending at $1$). Of course, $25-24-23-\ldots-3-2-1$ is longer. In fact, it is the longest one.

Input Format

The first line contains the number of rows $R$ and columns $C$ of the 2D array representing the area. The next $R$ lines each contain $C$ numbers, representing elevations (two numbers are separated by 1 space).

Output Format

Output the length of the longest downhill run in the area.

5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9

25

Hint

For $100\%$ of the testdata, $1 \le R, C \le 100$.

Translated by ChatGPT 5