Η Ξανθίππη έγραψε ένα άρθρο και θέλει να το διαβάσει όσο το δυνατόν περισσότερος κόσμος. Έχει Ν φίλους, ο καθένας απ' τους οποίους όταν διαβάσει το άρθρο είτε θα το στείλει σε ακριβώς έναν γνωστό του, είτε δε θα το στείλει πουθενά.
Η Ξανθίππη θέλει να στείλει το άρθρο σε έναν φίλο της, κι αυτός με την σειρά του να το δώσει στον επόμενο, και στον επόμενο, και στον επόμενο...
Το πρόβλημά σας είναι να βοηθήσετε την Ξανθίππη να διαλέξει έτσι τον φίλο στον οποίο θα δώσει το άρθρο ώστε να μεγιστοποιηθεί το πλήθος των ατόμων που θα το διαβάσουν.
Παράδειγμα :
Έστω ότι ο Βαγγέλης διαβάζοντας το άρθρο, το στέλνει στον Γιάννη. Ο Γιάννης το στέλνει στον Billy κι ο Billy στον Γιάννη.
Επομένως αν η Ξανθίππη δώσει το άρθρο στον Γιάννη ( ή στον Billy ) αυτό θα περάσει μόνο από δύο άτομα, ενώ αν το δώσει στον Βαγγέλη, θα περάσει από 3.
Η πρώτη γραμμή περιέχει τον αριθμό Ν, το πλήθος των φίλων της Ξανθίππης.
Οι επόμενες Ν γραμμές περιέχουν από έναν αριθμό.
Η i-οστη από αυτές τις γραμμές περιλαμβάνει το άτομο στο οποίο ο i-οστός φίλος της Ξανθίππης θα δώσει το άρθρο ( θα περιέχει τον αριθμό i αν αυτός δεν στέλνει πουθενά το άρθρο ).
Αποτελείται από μία μόνο γραμμή που περιέχει έναν αριθμό, το μέγιστο πλήθος ανθρώπων που γίνεται να διαβάσουν το άρθρο.
1 <= Ν <= 100.000
Στο 50% των testcases θα ισχύει N<=10.000
3 2 3 2
3
Αν η Ξανθίππη στείλει το άρθρο στον 1, τότε θα έχουμε 1-2-3-2-3-2-... άρα συνολικά θα το διαβάσουν 3 άτομα.
Αν το στείλει στον 2, τότε 2-3-2-3-2... άρα συνολικά 2 άτομα.
Αν το στείλει στον 3, τότε 3-2-3-2-3... άρα συνολικά 2 άτομα.
Συνεπώς η καλύτερη απάντηση είναι 3.
6 2 3 4 5 5 4
5
1-2-3-4-5-5-5... άρα 5 άτομα, που είναι και η βέλτιστη λύση.