Problem Description

JOI is playing on the beach. He has built a sandcastle on a rectangular area of the beach. This rectangular area has \( H \) rows and \( W \) columns. The height of the grid at the \( i \)-th row from the top and the \( j \)-th column from the left is \( A_{i, j} \). Note that all \( A_{i, j} \) values are distinct.

On the sandcastle, JOI performs the following actions:

1. First, JOI selects a grid and starts moving from that grid.
2. Then, he moves from the current grid to an adjacent grid in one of the four directions: up, down, left, or right. He must move to a grid that is lower than the current grid. He can repeat this action zero or more times.

Ultimately, if we look from above, the grids he passes through will form a rectangle.

Given the height information \( A_{i, j} \) of each grid, write a program to calculate the number of all possible rectangles that JOI can pass through.

Input Format

The first line contains two positive integers \( H \) and \( W \).

The next \( H \) lines contain \( W \) positive integers each, where the \( i \)-th line contains \( A_{i, 1}, A_{i, 2}, \ldots, A_{i, W} \).

Output Format

Output a single line containing a single number, which is the number of all possible rectangles that JOI can pass through.

Sample Input and Output

Sample Input #1

1 5
2 4 7 1 5

Sample Output #1

10

Sample Input #2

3 2
18 10
19 12
17 13

Sample Output #2

15

Sample Input #3

3 5
83 47 36 38 40
13 10 26 68 67
15 19 20 70 90

Sample Output #3

65

Notes

[Sample Explanation #1]

Since there are 10 possible rectangles that JOI can pass through, output 10.

[Sample Explanation #2]

Since there are 15 possible rectangles that JOI can pass through, output 15.

[Sample Explanation #3]

For example, the following rectangle can be formed by the grids JOI passes through. Since there are 65 possible rectangles in total, output 65.

[Data Range]

This problem is group testing.

For \( 100\% \) of the data, \( 1 \le H, W, H \cdot W \le 5 \times 10^4 \), \( 1 \le A_{i, j} \le 10^7 \), \( A_{i_1, j_1} \ne A_{i_2, j_2} \) (\( (i_1, j_1) \ne (i_2, j_2) \)).

• Subtask 1 (9 points): \( H = 1 \).
• Subtask 2 (10 points): \( H \cdot W \le 100 \).
• Subtask 3 (5 points): \( H \cdot W \le 1500 \).
• Subtask 4 (56 points): \( H \cdot W \le 7000 \).
• Subtask 5 (20 points): No additional constraints.

Translated from JOI 2022 Final T5 "砂の城 2 / Sandcastle 2"

见题面 Input 部分

见题面 Output 部分