ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

USU Personal Contest 2004

About     Problems     Submit solution     Judge status     Standings
Contest is over

B. Space Poker

Time limit: 1.0 second
Memory limit: 64 MB
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 |XY| ≤ 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
  1. All the cards of one suit lie one after another.
  2. Blue and yellow suits alternate (this is always possible due to the Steinpuper rule).
  3. 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.

Input

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.

Output

The output should contain the minimal number of operations necessary for arranging the cards.

Sample

inputoutput
5
10 1
12 2
8 2
4 4
7 4
2
Problem Author: Leonid Volkov
Problem Source: USU Personal Contest 2004
To submit the solution for this problem go to the Problem set: 1284. Space Poker