Ammunition Storage

Time limit2sMemory limit1024 MB

Summary

Count the sub-rectangles of at least 2 by 2 whose four corner cells are taller than every other cell inside the rectangle.

Level: Hard8 of 10
Topics: Matrix, Linked list, Sorting
Solved: No attempts yet

Problem

The Do-Barareh military area is an n×m grid, and each cell has a fixed height. The commander of this area wants to find a rectangular sub-area whose width and height are both at least 2, and whose four corner cells are higher than all other cells in the sub-area. The commander will install watchtowers at the corners to monitor the whole sub-area and use it as an ammunition storage. Count how many valid sub-areas can be chosen as the ammunition storage. You may assume all cell heights are distinct.

Input

The first line contains two space-separated integers $n$ and $m$ ( $2 \le n, m \le 750$ ). Each of the next $n$ lines contains $m$ space-separated integers, the heights of the cells. All cell heights are distinct integers between 1 and $nm$ (inclusive).

Output

Print the number of valid sub-areas that can be used as an ammunition storage.

Examples1

Example 1
Input
```
3 3
9 4 8
2 1 3
7 5 6
```
Expected output
```
7
```