Delivery — Eolymp

Eingabe

From the first line of the standard input, your program should read one integer $N$ – the number of queries. Each of the next $N$ lines will contain two integers $T_{i}$ T_{i} and $H_{i}$ H_{i} – the time and house the delivery should happen at.

Ausgabe

On a single line, your program should output the minimum number of delivery trucks that are needed.

Beispiele

Beispiel 1

Loading

Notiz

The minimum number of delivery trucks we need is 2. One way to complete all deliveries is:

First truck: $(1, 1)^{*} \to (2, 1) \to (3, 1) \to (4, 1)^{*} \to (5, 1)$ (1, 1)^* \to (2, 1) \to (3, 1) \to (4, 1)^* \to (5, 1)

Second truck: $(1, 2) \to (2, 3)^{*} \to (3, 2)^{*} \to (4, 3)^{*} \to (5, 4)^{*}$ (1, 2) \to (2, 3)^* \to (3, 2)^* \to (4, 3)^* \to (5, 4)^*

Where $(t, h)$ represents the truck being at house $h$ at time $t$ , and $*$ are times on which the truck makes a delivery.

Bewertung

1 \leq N \leq 1 0^{6}

1 \leq N \leq 10^{6}

1 \leq T_{i}, H_{i} \leq 1 0^{9}

1 \leq T_{i}, H_{i} \leq 10^{9}

T_{i} \neq = T_{j} or H_{i} \neq = H_{j} for i \neq = j

T_{i} \neq T_{j} \text{ or } H_{i} \neq H_{j} \text{ for } i \neq j

Subtask	Points	$N$
1	25	$\leq 1 0^{3}$ \leq 10^{3}
2	10	$\leq 1 0^{4}$ \leq 10^{4}
3	40	$\leq 2 \times 1 0^{5}$ \leq 2 \times 10^{5}
4	20	$\leq 1 0^{6}$ \leq 10^{6}