Problem Statement

Longest Increasing Grid Path with One Dash You are given an N by M integer grid. A path may start at any cell. Every move must land on a cell whose value is strictly greater than the current cell's value. Normally, a move goes one cell up, down, left, or right. During the entire path, you may use at most one **Dash**: move exactly two cells in one cardinal direction. The intermediate cell is ignored, need not have any particular value, and is not counted as visited. Find the maximum number of visited cells. Input The first line contains N . The second line contains M . Each of the next N lines contains M grid values. Output Print the maximum possible number of visited cells. Constraints 1 <= N, M N*M <= 200000 -10^9 <= grid[i][j] <= 10^9 The answer fits in a 32-bit signed integer. Examples Input: 3 3 1 2 3 6 5 4 7 8 9 Output: 9 The path can visit values 1,2,3,4,5,6,7,8,9 without using the dash. Input: 3 3 1 2 100 3 4 5 6 7 8 Output: 6 For example, visit 1,3,4,5,8 , the