Sandcastle 2

Time limit4sMemory limit1024 MB

Summary

Count the rectangles whose cells can be visited by a path that steps only to adjacent cells with strictly lower heights.

Level: Hard9 of 10
Topics: Sorting, Divide and conquer, Implementation
Solved: No attempts yet

Problem

JOI-kun is playing on a sand beach and makes a sandcastle. The sandcastle lies in a rectangular region of sand made of $H$ rows and $W$ columns of cells. The cell in the $i$ -th row from the north and the $j$ -th column from the west has height $A_{i,j}$ . All heights are different from each other.

JOI-kun performed the following actions. First, he chose a cell and started moving from it. Then he moved from the current cell to an adjacent cell in one of the four directions. The cell he moved to had to be lower than the current cell. He repeated this zero or more times.

Finally, if you view the cells he visited from above, they form a rectangle. Count the number of possible rectangles formed by the cells JOI-kun visited.

Input

The first line contains two integers $H$ and $W$ . Each of the next $H$ lines contains $W$ integers, where the $j$ -th integer on the $i$ -th line is $A_{i,j}$ .

Output

Print one line containing the number of possible rectangles formed by the cells JOI-kun visited.

Constraints

$H \ge 1$ , $W \ge 1$ , $H \times W \le 50\,000$ , and $1 \le A_{i,j} \le 10\,000\,000$ for all $i$ and $j$ . Any two different cells have different heights.

Examples3

Example 1
Input
```
1 5
2 4 7 1 5
```
Expected output
```
10
```
Example 2
Input
```
3 2
18 10
19 12
17 13
```
Expected output
```
15
```

Example 3

Input

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

Expected output