Milano C.le

Η Σίλβια βρίσκεται στον σιδηροδρομικό σταθμό Milano Centrale και παρατήρησε ότι ο σταθμός έχει πολλές πλατφόρμες. Σκέφτηκε ότι υπάρχουν υπερβολικά πολλές, και αποφάσισε να ελέγξει πόσες ακριβώς από αυτές χρειάζονται πραγματικά.

Η Σίλβια παρατήρησε επίσης ένα ενδιαφέρον γεγονός που ισχύει για αυτόν το σταθμό: το πρόγραμμα άφιξης και αναχώρησης επαναλαμβάνεται κάθε δύο ημέρες, και επιπλέον, το πρόγραμμα είναι τέτοιο ώστε όλα τα ~n~ τρένα να φτάνουν στο σταθμό σε μια μέρα και να αναχωρούν την επόμενη. Παρατηρήστε ότι με αυτόν τον τρόπο κανένα τρένο δεν θα αναχωρήσει πριν να φτάσουν όλα τα τρένα στο σταθμό.

Οι πλατφόρμες στον σταθμό είναι αρκετά μεγάλες ώστε και τα ~n~ τρένα να μπορούν να τοποθετηθούν το ένα μετά το άλλο στην ίδια πλατφόρμα. Ωστόσο, αν το τρένο ~x~ μπει πρώτο στην πλατφόρμα και στη συνέχεια μπει το τρένο ~y~, τότε το τρένο ~x~ δεν μπορεί να φύγει από την πλατφόρμα πριν από το τρένο ~y~.

Το σχήμα δείχνει έναν πιθανό προγραμματισμό των τρένων στις πλατφόρμες του δεύτερου παραδείγματος. Οι ετικέτες στα τρένα '~i: a_{i}/b_{i}~' υποδεικνύουν ότι το ~i~-οστό τρένο θα φτάσει στο σταθμό ~a_{i}~-οστό την πρώτη μέρα και θα αναχωρήσει από το σταθμό ~b_{i}~-οστό τη δεύτερη μέρα. Το τρένο ~(2:\;1/2)~ δεν μπορεί να αναχωρήσει από την πλατφόρμα πριν από το τρένο ~(4:\;5/1)~.

Η Σίλβια ενδιαφέρεται να μάθει ποιος είναι ο ελάχιστος αριθμός πλατφορμών που χρειάζονται έτσι ώστε όλα τα τρένα να μπορούν να τοποθετηθούν στις πλατφόρμες, χωρίς να υπάρχει το ενδεχόμενο να μην μπορεί ένα τρένο να αποχωρήσει από την πλατφόρμα επειδή υπάρχει ένα τρένο μπροστά του που δεν έχει φύγει ακόμα.

Είσοδος

Η πρώτη γραμμή της εισόδου θα περιέχει έναν ακέραιο ~n\;(1 \le n \le 2 \times 10^{5})~, τον αριθμό των τρένων.

Η δεύτερη γραμμή θα περιέχει ~n~ ακεραίους ~a_{i}~, ~(1 \le a_{i} \le n~,~\; a_{i} \neq a_{j}~ για όλα τα ~i \neq j~), οι οποίοι υποδεικνύουν ότι το ~i~-οστό τρένο φτάνει στο σταθμό ως το ~a_{i}~-οστό τρένο την πρώτη μέρα. Η ακολουθία (~a_{i}~) είναι μια μετάθεση.

Η τρίτη γραμμή θα περιέχει ~n~ ακεραίους ~b_{i}~, ~(1 \le b_{i} \le n,\; b_{i} \neq b_{j}~ για όλα τα ~i \neq j~), οι οποίοι υποδεικνύουν ότι το ~i~-οστό τρένο αποχωρεί από το σταθμό ως το ~b_{i}~-οστό τρένο τη δεύτερη μέρα. Η ακολουθία (~b_{i}~) είναι μια μετάθεση.

Έξοδος

Στην πρώτη και μοναδική γραμμή εξόδου θα πρέπει να εκτυπώσετε τον ελάχιστο αριθμό πλατφορμών που απαιτούνται.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
~1~	~21~	~n \le 10~
~2~	~18~	Ο ελάχιστος αριθμός πλατφορμών που απαιτούνται θα είναι ~1~ ή ~2~
~3~	~31~	~n \le 1000~
~4~	~40~	Κανένας επιπλέον περιορισμός

Παραδείγματα

input

5
3 1 2 5 4
4 2 3 1 5

output

4

Επεξήγηση του πρώτου παραδείγματος:

Ρίξτε μια ματιά στο σχήμα που περιλαμβάνεται στην περιγραφή.

input

5
3 5 2 4 1
3 2 5 1 4

output

2

input

3
3 2 1
1 2 3

output

1

Επεξήγηση του τρίτου παραδείγματος:

Όλα τα τρένα μπορούν να παραταχθούν στην ίδια πλατφόρμα χωρίς κανένα πρόβλημα.