JOI đang chơi xây lâu đài cát trên bãi biển. Lâu đài nằm trong một vùng hình chữ nhật trên cát. Vùng này được biểu diễn bằng một lưới có \(H\) hàng và \(W\) cột: các hàng được đánh số từ bắc xuống nam, các cột từ tây sang đông. Ô ở hàng \(i\) (\(1 \le i \le H\)), cột \(j\) (\(1 \le j \le W\)) có độ cao \(A_{i,j}\). Độ cao của tất cả các ô đôi một khác nhau.

Trên lâu đài cát này, JOI thực hiện các hành động sau:

1. Chọn một ô bất kỳ làm điểm xuất phát.
2. Từ ô hiện tại, di chuyển tới một ô kề cạnh theo một trong bốn hướng đông, tây, nam, bắc có độ cao nhỏ hơn. Lặp lại hành động này không hoặc nhiều lần.

Sau cùng, khi nhìn từ trên xuống, toàn bộ các ô mà JOI đã ghé qua tạo thành đúng một vùng hình chữ nhật.

Cho độ cao của các ô, hãy đếm số vùng hình chữ nhật khác nhau có thể là tập hợp các ô JOI đã ghé qua.

Dữ liệu vào

Dữ liệu được cho từ đầu vào chuẩn theo định dạng:

H W
A_{1,1} A_{1,2} ... A_{1,W}
A_{2,1} A_{2,2} ... A_{2,W}
...
A_{H,1} A_{H,2} ... A_{H,W}

Tất cả các giá trị đầu vào đều là số nguyên.

Dữ liệu ra

In ra một dòng chứa số vùng hình chữ nhật khác nhau có thể là tập hợp các ô mà JOI đã ghé qua.

Ràng buộc

• \(H \ge 1\).
• \(W \ge 1\).
• \(H \times W \le 50\,000\).
• \(1 \le A_{i,j} \le 10\,000\,000\) với mọi \(1 \le i \le H\), \(1 \le j \le W\).
• \(A_{i_1,j_1} \ne A_{i_2,j_2}\) với mọi hai ô phân biệt \((i_1,j_1) \ne (i_2,j_2)\).

Phân nhóm

• Nhóm 1 (9 điểm): \(H=1\).
• Nhóm 2 (10 điểm): \(H \times W \le 100\).
• Nhóm 3 (5 điểm): \(H \times W \le 1500\).
• Nhóm 4 (56 điểm): \(H \times W \le 7000\).
• Nhóm 5 (20 điểm): Không có ràng buộc bổ sung.

Ví dụ

1 5
2 4 7 1 5

10

3 2
18 10
19 12
17 13

15

3 5
83 47 36 38 40
13 10 26 68 67
15 19 20 70 90

65

Nguồn

JOI 2021/2022, vòng chung kết, ngày 13/02/2022. Đề gốc của Ủy ban Olympic Tin học Nhật Bản: tiếng Nhật, tiếng Anh. Bản dịch theo giấy phép CC BY-SA 4.0.