Problem Description

JOI is playing by building a sandcastle on the beach. The castle he built is contained within a rectangular area on the beach. This rectangular area is represented as a grid divided into $H$ rows and $W$ columns, with the vertical direction parallel to the north-south direction and the horizontal direction parallel to the east-west direction. The height of the square in the $i$-th row from the north ($1 \leq i \leq H$) and the $j$-th column from the west ($1 \leq j \leq W$) is $A_{i, j}$. Note that all values of $A_{i, j}$ are distinct.

For this sandcastle, JOI performed the following actions:

1. He chose a square and started from the top of that square.
2. Then, he repeatedly moved to a lower adjacent square to the east, west, north, or south, zero or more times.

When viewed from above, the region of squares JOI visited eventually forms a single rectangle.

Given the height information $A_{i, j}$ for each square, write a program to determine how many possible rectangular regions of squares JOI could have visited.

Input Format

The input is given from the standard input in the following format. All values are integers.

$H$ $W$ $A_{1, 1}$ $A_{1, 2}$ $\cdots$ $A_{1, W}$ $A_{2, 1}$ $A_{2, 2}$ $\cdots$ $A_{2, W}$ $\vdots$ $A_{H, 1}$ $A_{H, 2}$ $\cdots$ $A_{H, W}$

Output Format

Output a single line to the standard output, the number of possible rectangular regions JOI could have visited.

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/Hints

Constraints

• $H \geq 1$.
• $W \geq 1$.
• $H \times W \leq 50,000$.
• $1 \leq A_{i, j} \leq 10,000,000$ ($1 \leq i \leq H$, $1 \leq j \leq W$).
• $A_{i_1, j_1} \neq A_{i_2, j_2}$ ($1 \leq i_1 \leq H$, $1 \leq j_1 \leq W$, $1 \leq i_2 \leq H$, $1 \leq j_2 \leq W$, $(i_1, j_1) \neq (i_2, j_2)$).

Subtasks

1. ($9$ points) $H = 1$.
2. ($10$ points) $H \times W \leq 100$.
3. ($5$ points) $H \times W \leq 1,500$.
4. ($56$ points) $H \times W \leq 7,000$.
5. ($20$ points) No additional constraints.

Sample Explanation 1

There are $10$ possible rectangular regions JOI could have visited, so output $10$.

Sample Explanation 2

There are $15$ possible rectangular regions JOI could have visited, so output $15$. This example satisfies the constraints of Subtasks $2, 3, 4, 5$.

Sample Explanation 3

For example, the following rectangular region is possible. Including others, there are $65$ in total, so output $65$. This example satisfies the constraints of Subtasks $2, 3, 4, 5$.

见题面 Input 部分

见题面 Output 部分