Block and escape! P16544

Statement

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:

0.7

(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)

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

0.3

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, \dots, a_n$ and $b_1, b_2, \dots, b_n$ . All the given numbers are integers. There are no repeated $a_i$ ’s nor repeated $b_i$ ’s. Assume $1 \le n \le 10^5$ and $1 \le a_i, b_i \le 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++