샌드캐슬 2

JOI-kun은 모래사장에서 놀면서 모래성을 만든다. 모래성은 $H$개의 행과 $W$개의 열로 이루어진 직사각형 모래 영역 안에 있다. 북쪽에서 $i$번째 행, 서쪽에서 $j$번째 열에 있는 칸의 높이는 $A_{i,j}$이다. 모든 높이는 서로 다르다.

JOI-kun은 다음 행동을 했다. 먼저 칸 하나를 골라 그 칸에서 출발했다. 그다음 현재 칸에서 상하좌우 중 한 방향의 인접한 칸으로 이동했다. 이동할 칸은 현재 칸보다 반드시 낮아야 한다. 이 이동을 0번 이상 반복했다.

그 결과 방문한 칸들을 위에서 보면 직사각형을 이룬다. JOI-kun이 방문한 칸들로 만들 수 있는 직사각형의 개수를 구하라.

첫 줄에 정수 $H$와 $W$가 주어진다. 이어지는 $H$개의 줄에는 각각 $W$개의 정수가 주어지며, $i$번째 줄의 $j$번째 정수가 $A_{i,j}$이다.

JOI-kun이 방문한 칸들로 만들 수 있는 직사각형의 개수를 한 줄에 출력한다.

$H \ge 1$, $W \ge 1$, $H \times W \le 50\,000$, 모든 $i$, $j$에 대해 $1 \le A_{i,j} \le 10\,000\,000$이다. 서로 다른 두 칸의 높이는 항상 다르다.