Background

Cirno made a new game called “Tales of Cyansis Pearl”.

Game example (Sample #1):

Problem Description

The rules are as follows:

At the beginning, there is an $n \times n$ grid, and each cell contains one Cyansis Pearl.

There are $n$ colors in total. For each color, there are exactly $n$ pearls, distributed uniformly at random in the $n \times n$ grid.

Each time, the player may choose several consecutive pearls of the same color on the bottom row of the grid and remove them.

After removal, the pearls above will fall down due to gravity.

The player repeats the above operation until all pearls are removed. Then the game ends.

Now, Cirno gives you a uniformly random initial board of the game Tales of Cyansis Pearl. Find the minimum number of moves to finish the game.

Input Format

The first line contains an integer $n$.

The following $n$ lines each contain $n$ integers, each in the range $[1, n]$.

It is guaranteed that each integer appears exactly $n$ times.

Output Format

Output one line containing an integer, the minimum number of moves.

3
1 1 2
2 3 1
3 2 3

5

5
2 1 4 4 2
2 5 5 1 3
4 1 3 5 1
3 2 5 3 5
1 4 4 2 3

15

Hint

For $100\%$ of the testdata, $1 \le n \le 1000$. The input is guaranteed to be randomly generated.

Reprinted from XDUCPC 2021 Onsite Contest J.

Translated by ChatGPT 5