C. Fill the World with Argon
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Unlike BAPC, Teamscode has enough funds to fill not just the gym, but the entire world with argon.

The world is represented by a grid of size $$$N \times M$$$. To help with filling the world with argon, you are given a 2D map, where $$$a_{i,j}$$$ represents the height of each of the cell in the $$$i$$$-th row and $$$j$$$-th column. All heights are distinct.

When you pour argon on a cell, it becomes filled with argon. Argon then flows from a filled cell to any of its adjacent cells (up, down, left, right) that have a lower height, causing them to fill with argon too. This filling process continues recursively until no further cells can be filled from that drop.

Determine the minimum number of cells you need to pour argon on to fill the entire world with argon.

Input

The first line contains two integers $$$N$$$, $$$M$$$ ($$$1 \le N, M \le 1000$$$) – the number of rows and columns, respectively, in $$$a$$$.

Then $$$N$$$ lines follow, the $$$i$$$-th line containing $$$M$$$ integers $$$a_{i, 1}, a_{i, 2}, \ldots, a_{i, m}$$$ ($$$0 \le a_{i, j} \le 10^9$$$), representing the height of the cell in the $$$i$$$-th row and $$$j$$$-th column.

—

Tests in subtasks are numbered from $$$1−20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.

Tests $$$1-20$$$ satisfy no additional constraints.

Output

One integer – the minimum number of cells you need to pour argon on to fill the entire world.

Example
Input
2 3
1 2 3
4 5 6
Output
1
Note

For the example test case, you can pour argon on the cell with height $$$6$$$.

This cell is next to cells with lower height $$$5$$$ and $$$3$$$, so those cells would get filled too.

The cell with height $$$5$$$ is next to cells with lower height $$$4$$$ and $$$2$$$, so those cells would get filled too.

The cell with height $$$4$$$ is next to the cell with lower height $$$1$$$, so that cell would get filled too.

After the pour, all the cells are filled with argon. Thus, only one pour is necessary.

—

Problem Idea: Alex_C

Problem Preparation: n685

Occurrences: Novice C