Description

There are $n$ wooden sticks in total, and the length and width of each stick are known. The sticks can be processed by a machine one after another. Before processing a stick, the machine may need setup time. The setup time is defined as follows:

• The setup time for the first stick is $1$ minute.
• If the just-processed stick has length $l$ and width $w$, then for the next stick with length $l_i$ and width $w_i$, if $l \ge l_i$ and $w \ge w_i$, no setup time is needed; otherwise, $1$ minute of setup time is needed.

Compute the minimum total setup time needed to process all $n$ sticks. For example, if you have $5$ sticks with lengths and widths $(4, 9), (5, 2), (2, 1), (3, 5), (1, 4)$, the minimum setup time is $2$ (process in the order $(4, 9), (3, 5), (1, 4), (5, 2), (2, 1)$).

Input Format

The first line contains an integer $n$ ($n \le 5000$).

The second line contains $2n$ integers: $l_1, w_1, l_2, w_2, \ldots, l_n, w_n$. The values of $l$ and $w$ do not exceed $10000$, and adjacent numbers are separated by spaces.

Output Format

A single line containing one integer: the minimum total setup time required.

5
4 9 5 2 2 1 3 5 1 4

2

Hint

For $100 \%$ of the testdata, $1 \le n \le 5000$, $1 \le l_i, w_i \le 10^4$.

Translated by ChatGPT 5