Problem Description

JOI is playing on the beach. He built a sandcastle. The sandcastle built by JOI is located in a rectangular area on the beach. This rectangular area has $H$ rows and $W$ columns. The height of the cell in the $i$-th row from top to bottom and the $j$-th column from left to right is $A_{i, j}$. Note that all values of $\boldsymbol{A_{i, j}}$ are pairwise distinct.

On the sandcastle, JOI performs the following actions.

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

In the end, if we look from above, the cells he has visited will form a rectangle.

Given the height information $A_{i, j}$ of each cell, write a program to compute the number of all possible rectangles that can be formed by the cells visited by JOI.

Input Format

The first line contains two positive integers $H, W$.

The next $H$ lines follow. The $i$-th line contains $W$ positive integers $A_{i, 1}, A_{i, 2}, \ldots, A_{i, W}$.

Output Format

Output one line with a single integer, representing the number of all possible rectangles formed by the cells visited by JOI.

1 5
2 4 7 1 5

10

3 2
18 10
19 12
17 13

15

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

65

Hint

[Sample Explanation #1]

Since there are $10$ possible rectangles formed by the cells visited by JOI, output $10$.

This sample satisfies the constraints of all subtasks.

[Sample Explanation #2]

Since there are $15$ possible rectangles formed by the cells visited by JOI, output $15$.

This sample satisfies the constraints of subtasks $2, 3, 4, 5$.

[Sample Explanation #3]

For example, the following rectangle can be formed by the cells visited by JOI. Since there are $65$ possible rectangles in total, output $65$.

This sample satisfies the constraints of subtasks $2, 3, 4, 5$.

[Constraints]

This problem uses bundled testdata.

For $100\%$ of the testdata, $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」

Translated by ChatGPT 5