Parking Theory

문제

Sharif University has a rectangular parking lot with $n\times mn\; \backslash times\; m$ spaces for cars. Each row and column of the parking lot has entrances at both ends.

The parking lot is full, and the order in which the cars entered is given for each parking space. Specifically, a cell with the number $11$ is the first car that entered the parking lot, and a cell with the number $n\cdot mn\; \backslash cdot\; m$ is the last one to enter.

Abolfazl has a theory about how cars park in this lot. He believes that any car entering the parking lot from a specific side (row or column) moves straight until it finds its parking spot and never changes direction. Moreover, a car cannot pass through a cell that already contains a parked car.

Abolfazl wants to count the number of subgrids in the parking lot that satisfy this condition. A subgrid is valid if all cars in that subgrid can park without violating the above rules, considering only the cars within the subgrid.

Help Abolfazl determine the number of such valid subgrids.

입력

The first line of input contains two integers $nn$ and $mm$ ($1\le n,m\le 5001\; \backslash le\; n,\; m\; \backslash le\; 500$), the number of rows and columns of the parking lot. Each of the following $nn$ lines contains $mm$ integers, indicating the order of entry of the cars. It is guaranteed that numbers are different between $11$ and $n\cdot mn\; \backslash cdot\; m$.

출력

Print a single integer, the number of valid subgrids in the parking lot.

2 3
1 2 5
3 4 6

18