You find yourself at one end of a narrow corridor…But there is something at the other end, what is it? OMG! It is a huge scary monster! And it is getting closer! What will you do?

You look around and you find a small computer. Since you are fast with computers
(right?) and the monster is still far away (right?) you decide to take a look.
It is the control system of the corridor’s gates! There are *n* vertical blast
doors, with their left rail at *a*_{i} meters from you, and their right rail at
*b*_{i} meters from you.

You have an idea! Let’s shut the blast doors so that the monster will have
to break them all to get to you!
So you order the control system to shut *n* doors.
But you get this reply: “WA”.

Mmm…You cannot shut simultaneously two doors *i* and *j* that cross, that
is, such that *a*_{i} < *a*_{j} but *b*_{i} > *b*_{j}. Ah well, you can probably shut some
doors at least. For instance, this is one of the several optimum solutions (4
doors shut) for this corridor with 10 doors:

unit=0.15cm
(80,16)

(8,0)0.0100(8,0) (16,0)0.0101(16,0) (24,0)0.0102(24,0) (32,0)0.0103(32,0) (40,0)0.0104(40,0) (48,0)0.0105(48,0) (56,0)0.0106(56,0) (64,0)0.0107(64,0) (72,0)0.0108(72,0) (80,0)0.0109(80,0)

(8,16)0.0110(8,16) (16,16)0.0111(16,16) (24,16)0.0112(24,16) (32,16)0.0113(32,16) (40,16)0.0114(40,16) (48,16)0.0115(48,16) (56,16)0.0116(56,16) (64,16)0.0117(64,16) (72,16)0.0118(72,16) (80,16)0.0119(80,16)

linewidth=2pt

(1,0)(106,0) (1,16)(106,16)

-1002 -1503 -1607 -1908

linewidth=0.5pt linestyle=dashed

-1100 -1206 -1305 -1409 -1701 -1804

The computer has an editor and a compiler, so you can try to make a program to find the maximum number of doors that can be shut. But hurry! The huge scary monster is getting closer…

**Input**

Input consists of several cases.
Every case begins with the number of doors *n*,
followed by *a*_{1}, *a*_{2}, …, *a*_{n} and *b*_{1}, *b*_{2}, …, *b*_{n}.
All the given numbers are integers.
There are no repeated *a*_{i}’s nor repeated *b*_{i}’s.
Assume 1 ≤ *n* ≤ 10^{5} and 1 ≤ *a*_{i}, *b*_{i} ≤ 10^{9}.

**Output**

For every case, print the maximum number of doors that can be shut.

Public test cases

**Input**

10 1 2 3 4 5 6 7 8 9 10 3 1 7 6 10 4 8 2 5 9 3 30 20 10 300 200 100 3 200 100 300 20 30 10

**Output**

4 3 1

Information

- Author
- Marçal Garolera
- Language
- English
- Official solutions
- C++
- User solutions
- C++
- Event
- Setè Concurs de Programacio de la UPC - Final
- Date
- 2009-09-16