Minimal Moves in Colored Gems Grid

You are given an n × n grid where each cell contains a colored gem. There are n distinct colors and exactly n gems of each color. The gems are distributed uniformly at random in the grid.

The game is played as follows:

• At any move, you may select a contiguous block of gems of the same color from the bottom row of the grid and remove them.
• After removal, the gems above drop down due to gravity (i.e. each column behaves as a stack, and the removed gem is popped from that column).
• The game ends when all gems are removed from the grid.

Your task is: given an initial configuration, compute the minimum number of moves required to clear the grid.

Observations:

Since the gems fall independently within each column and every column starts with n gems, the order in which gems are removed from each column is fixed. In each move, you remove the bottom (current) gem from a set of contiguous columns if and only if they all have the same color.

Thus, if you label each column’s sequence (from bottom to top) as b[i][1...n] (where b[i][1] is the bottom gem in column i), then the optimal strategy is to remove gems level by level. At each level, from the bottom row (level 1) to the top (level n), you can remove a contiguous segment of gems in one move if they have the same color.

The minimum moves equals the sum, over each level i (from 1 to n), of the number of contiguous segments in that level. Note that if the grid is provided with the top row first and the bottom row last, then the i-th removal corresponds to the row at index n-i+1 of the input.

Input and Output Formats:

inputFormat

The first line contains an integer n (1 ≤ n ≤ 1000, for instance). Each of the next n lines contains n space-separated integers. These integers represent the colors of the gems in the grid. The grid is given row by row from top to bottom (i.e. the last line corresponds to the bottom row of the grid).

All colors are positive integers. It is guaranteed that each color appears exactly n times.

outputFormat

Output a single integer – the minimum number of moves needed to clear all the gems from the grid.

sample

2
1 2
1 1

3