정올이는 가로 W열, 세로 H행으로 이루어진 모래밭 위에 모래 성을 만들었다. 각 칸의 높이는 서로 다른 정수 A_{i,j}로 주어진다 (1 ≤ i ≤ H, 1 ≤ j ≤ W).

정올이는 다음과 같은 방식으로 모래 성 위를 이동한다:

이때 정올이가 최종적으로 방문한 모든 칸의 집합을 위에서 바라보면 언제나 속이 꽉 찬 하나의 직사각형을 이룬다.

주어진 높이 배열 A에 대해, 정올이가 방문한 칸들의 영역으로 만들 수 있는 직사각형의 개수를 구하라.

모래성 2 timer 4s memory 1024MB

모래성 2 4s 1024MB