Electric Wires

Interview

Time limit1sMemory limit128 MB

Summary

Given wires connecting positions on two poles, find the minimum removals so remaining wires never cross, equivalent to n minus the longest increasing subsequence.

Level: Medium5 of 10
Topics: Dynamic programming, Binary search, Sorting
Solved: No attempts yet

Problem

As wires were added one by one between poles A and B, some of the wires began to cross. Because crossing wires are unsafe, several wires must be removed so that no two remaining wires cross.

The connection points on each pole are numbered from top to bottom. Given the number of wires and the point on each pole where every wire is connected, write a program that finds the minimum number of wires that must be removed so that all remaining wires are non-crossing.

Input

The first line contains the number of wires. The number of wires is a positive integer no greater than 100.

Each of the next lines contains two integers: the position on pole A and the position on pole B connected by one wire, in that order. Every position number is a positive integer no greater than 500. No two wires are connected to the same position.

Output

Print one integer: the minimum number of wires that must be removed so that no two remaining wires cross.

Examples1

Example 1
Input
```
8
1 8
3 9
2 2
4 1
6 4
10 10
9 7
7 6
```
Expected output
```
3
```