The rules of playing space poker are so complicated that there’s no sense in trying to explain them here. We’ll say only that at the beginning of a game each player is given N (N ≤ 20) cards. Each card has a value (an integer from 1 to 100) and a suit (an integer from 1 to 10). All the cards are different. Suits with odd numbers are called blue and suits with even numbers are called yellow. The cards are dealt by a special card machine, which guarantees that the Steinpuper rule is satisfied. This rule says that if at the beginning of a game a player has X different blue suits and Y different yellow suits, then |X−Y| ≤ 1. The cards are given to a player one by one and the player puts them into his hand from left to right.
In order to become acquainted with his cards before the game starts, the player arranges the cards
. This means that by means of atomic operations
he attains such a disposition of his cards that
- All the cards of one suit lie one after another.
- Blue and yellow suits alternate (this is always possible due to the Steinpuper rule).
- Inside a suit the cards are ordered either in the ascending or in descending order and all the suits are ordered in the same way.
An atomic operation consists in taking one of the cards and moving it to any place (i.e., to the leftmost position, to the rightmost position, or between any two cards). Obviously, arranging the cards can be performed in many ways, but the aim is to do it with the minimal number of operations.
The first line contains the number of cards N. The following N lines describe the cards in the order in which they are given by the machine. Each card is described by its value and suit separated with a space.
The output should contain the minimal number of operations necessary for arranging the cards.
Problem Author: Leonid Volkov
Problem Source: USU Personal Contest 2004