Rectangles timer 6초 memory 1024MB

19세기 초, 왕 Hoseyngulu Khan Sardar는 Zangi 강을 내려보는 평원에 궁궐을 지으라고 명령했다.

평원은 n × m 격자칸으로 생각한다.

격자의 행들은 0부터 n - 1까지 번호가 붙어 있고, 열들은 0부터 m - 1까지 번호가 붙어있다.

행번호 i, 열번호 j에 있는 칸을 칸 (i, j)라고 부른다 (0 ≤ i ≤ n - 1, 0 ≤ j ≤ m - 1).

각 칸 (i, j)는 높이 값 a_i,j를 가진다.

Hoseyngulu Khan Sardar는 건축가들에게 궁궐을 지을 직사각형 영역을 찾도록 요구했다.

해당 영역은 격자의 경계에 있는 (행 0 혹은 n - 1, 열 0 혹은 m - 1) 칸을 포함하면 안된다.

따라서, 건축가들은 4개의 정수 r₁, r₂, c₁, c₂를 선택해야 한다 (1 ≤ r₁ ≤ r₂ ≤ n - 2, 1 ≤ c₁ ≤ c₂ ≤ m - 2).

그러면, r₁ ≤ i ≤ r₂이고 c₁ ≤ j ≤ c₂인 칸 (i, j)들을 포함하는 영역이 정해진다.

추가적으로, 어떤 영역은 영역 내의 모든 칸 에 대해 다음 조건이 만족될 때 (그리고 그때만) 유효한 것으로 간주된다.

- 행 i에서 영역에 인접한 두 칸(칸 (i, c₁ - 1)과 (i, c₂ + 1))과 열 j에서 영역에 인접한 두 칸(칸 (r₁ - 1, j)와 (r₂ + 1, j))을 생각하자. 칸 (i, j)의 높이는 앞의 4칸의 높이 모두 보다 작아야 (미만이어야) 한다.

궁궐로 유효한 영역의 개수(즉, 유효한 영역을 만드는 r₁, r₂, c₁, c₂의 가능한 개수)를 계산하는 프로그램을 작성하라.​