24478번 - Sandcastle 2 서브태스크다국어

JOI-kun is playing on a sand beach. He makes a sandcastle. The sandcastle made by JOI-kun is contained in a rectangular region in the sand beach. The rectangular region consists of cells of $H$ horizontal rows and $W$ vertical columns. The cell in the $i$-th row ($1 ≤ i ≤ H$) from the north and the $j$-th column ($1 ≤ j ≤ W$) from the west has height $A_{i,j}$. Note that the values of $A_{i, j}$ are different from each other.

To the sandcastle, JOI-kun performed the following actions.

1. First, JOI-kun chose a cell, and he started moving from the chosen cell.
2. Then, he moved from the current cell to an adjacent cell in one of the four direction. He had to move to a cell which is lower than the current cell. He repeated this zero or more times.

Finally, if we view the cells he visited from above, the cells form a rectangle.

Given the information of the height $A_{i, j}$ of each cell, write a program which calculates the number of possible rectangles formed by the the cells JOI-kun visited.

Read the following data from the standard input. Given values are all integers.

$\begin{align*}& 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}\end{align*}$

Write one line to the standard output. The output should contain the number of possible rectangles formed by the cells JOI-kun visited.

• $H ≥ 1$.
• $W ≥ 1$.
• $H \times W ≤ 50\,000$.
• $1 ≤ A_{i, j} ≤ 10\,000\,000$ ($1 ≤ i ≤ H$, $1 ≤ j ≤ W$).
• $A_{i_1, j_1} \ne A_{i_2, j_2}$ ($1 ≤ i_1 ≤ H$, $1 ≤ j_1 ≤ W$, $1 ≤ i_2 ≤ H$, $1 ≤ j_2 ≤ W$, $(i_1, j_1) \ne (i_2, j_2)$).