As power lines were added one by one between two utility poles $A$ and $B$, some of them began to cross. Because of the risk of a short circuit, we want to remove some of these lines so that no lines cross.

For example, when the lines are connected as in Figure 1, removing the line from position $1$ on $A$ to position $8$ on $B$, the line from position $3$ on $A$ to position $9$ on $B$, and the line from position $4$ on $A$ to position $1$ on $B$ leaves no crossings among the remaining lines.

The positions where lines connect to a pole are numbered consecutively from top to bottom. Given the number of lines and the position numbers where they connect to the two poles, write a program to find the minimum number of lines that must be removed so that none of the remaining lines cross.

Input

The first line contains the number of power lines between the two poles. This is a positive integer at most $100$.

Starting from the second line, each line gives, in order, the position number where a power line connects to pole $A$ and the position number where it connects to pole $B$.

Each position number is a positive integer at most $500$, and two or more lines cannot connect at the same position.

Output

On the first line, output the minimum number of lines that must be removed so that no remaining lines cross.

Examples

Input 1

8
1 8
3 9
2 2
4 1
6 4
10 10
9 7
7 6

Output 1

3