Στο γκέτο της Χελενικούπολης, όλες οι πολυκατοικίες είναι στη σειρά, ενώ επίσης όλες έχουν διαφορετικό ύψος. Στην κορυφή κάθε πολυκατοικίας κάθεται ένας πράκτορας ο οποίος κοιτάει προς τα δεξιά σε ευθεία γραμμή( μπορούμε να φανταστούμε την ευθεία των πολυκατοικιών σαν τον άξονα των x) και έτσι βλέπει την πρώτη πολυκατοικία( αν υπάρχει ) που είναι ψηλότερη από αυτόν. Οι πολυκατοικίες είναι αριθμημένες από το 1 ως το N από αριστερά προς τα δεξιά. Μπορούμε να υποθέσουμε ότι τα ύψη των πολυκατοικιών επίσης είναι από 1 ως N. Οι κάτοικοι του γκέτο της Χελενικούπολης, εφόσον δεν ξέρουν άμεσα όλα τα ύψη των πολυκατοικιών αλλά μπορούν να αντλήσουν πληροφορία μόνο από το πού κοιτάει ο κάθε πράκτορας, θέλουν κάποια στατιστικά στοιχεία για τα ύψη των πολυκατοικιών. Έτσι θέλουν να μάθουν για κάθε k, πόσες πολυκατοικίες μπορούν να είναι k-οστές αν ταξινομήσουμε τις πολυκατοικίες κατά αύξουσα σειρά ύψους. Με άλλα λόγια, αν f_k = {πλήθος των πολυκατοικιών u για τις οποίες υπάρχει μια ανάθεση των υψών στις πολυκατοικίες ώστε η u να έχει τον αριθμό k}, Θέλουμε να τυπώσουμε τον αριθμό f_k,για κάθε k.
Στην πρώτη γραμμή δίνεται ένας ακέραιος αριθμός Ν, το πλήθος των πολυκατοικιών. Ακολουθούν Ν-1 γραμμές. Στην i-οστή γραμμή δίνεται ποια πολυκατοικία βλέπει η i-οστή πολυκατοικία. Αν δεν βλέπει καμία, αλλά βλέπει το άπειρο, θα έχει τον αριθμό N+1. H τελευταία πολυκατοικία παραλείπεται, γιατί πάντα βλέπει τον αριθμό Ν+1. Η αρίθμηση των πολυκατοικιών είναι από 1 ως Ν, από τα αριστερά προς τα δεξιά.
Ν γραμμές, όπου στην k-οστή γραμμή θα υπάρχει ο αριθμός f_k.
1<=Ν<=100
3 2 4
2 2 1
H ψηλότερη πολυκατοικία σίγουρα είναι η 2, άρα f_3 = 1. Από τις άλλες δύο, οποιαδήποτε μπορεί να είναι μικρότερη από την άλλη, δηλαδή είτε πρώτη είτε δεύτερη, άρα f_1 = f_2 = 2.
7 8 8 8 8 8 8
1 1 1 1 1 1 1
Οι πολυκατοικίες είναι σε φθίνουσα σειρά ύψους, όπως εύκολα διαπιστώνει κανείς, άρα υπάρχει μία και μοναδική έγκυρη τοποθέτηση των υψών στις πολυκατοικίες, πράμα που δίνει άμεσα ότι όλα τα f_k ισούνται με 1.