Volontiranje

Δεν είναι γενικά γνωστό ότι στον ελεύθερο χρόνο του, ο κ. Malnar, συνεισφέρει στην κοινότητα μέσω του εθελοντισμού. Ακριβώς! Είναι αρκετά ενεργός στο εθελοντικό κέντρο για προβλήματα πληροφορικής.

Πρόσφατα έλαβε ένα τηλεφώνημα από το κέντρο και όπως αποδεικνύεται υπάρχει έλλειψη σε αυξανόμενες αλληλουχίες. Ο κ. Malnar, που είναι πάντα πρόθυμος να βοηθήσει, ανταποκρίθηκε άμεσα. Πιο συγκεκριμένα, διατηρεί έναν πίνακα ~n~ ακεραίων για αυτόν ακριβώς τον σκοπό. Όλοι οι ακέραιοι αριθμοί από το 1 έως το ~n~ εμφανίζονται ακριβώς μία φορά στον πίνακα του.

Ο κ. Malnar θα επιλέξει μερικές αυξανόμενες υποακολουθίες από τον πίνακά του, τις οποίες θα δωρίσει στο κέντρο, και θα κρατήσει τους υπόλοιπους αριθμούς για κάποια άλλη στιγμή. Πρέπει να σημειωθεί ότι κάθε αριθμός από τον πίνακα μπορεί να χρησιμοποιηθεί το πολύ για μία υποακολουθία, δηλαδή οι επιλεγμένες υποακολουθίες έχουν διακριτούς δείκτες.

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

Επειδή ο κύριος Malnar είναι πολύ γενναιόδωρος, θέλει όλες οι ακολουθίες που δωρίζει να είναι οι μεγαλύτερες αυξανόμενες υποακολουθίες. Με άλλα λόγια, αν ~l~ είναι το μήκος της μεγαλύτερης αυξανόμενης υποακολουθίας του αρχικού πίνακα, ο κ. Malnar θα επιλέξει μερικές ασύνδετες αυξανόμενες υποακολουθίες, η καθεμία μήκους ~l~.

Ο κ. Malnar θέλει να δωρίσει όσο το δυνατόν περισσότερες υποακολουθίες. Για έναν δεδομένο πίνακα του κ. Malnar, εκτυπώστε το μέγιστο αριθμό υποακολουθιών που αποτελούν την επιλογή του και παράξτε ένα παράδειγμα τέτοιου είδους επιλογής.

Είσοδος

Η πρώτη γραμμή περιέχει τον ακέραιο ~n~ - το μέγεθος του πίνακα.

Η δεύτερη γραμμή περιέχει ~n~ αριθμούς ~p_i~ ~(1 \le p_i \le n)~ που αντιπροσωπεύουν τα στοιχεία του πίνακα. Καθε θετικός ακέραιος ~j~ μεταξύ 1 και ~n~ εμφανίζεται ακριβώς μία φορά στον πίνακα.

Έξοδος

Στην πρώτη γραμμή, εκτυπώστε τον μεγαλύτερο δυνατό αριθμό υποακολουθιών στην επιλογή του κ. Malnar, καθώς και το μήκος της μεγαλύτερης αυξανόμενης υποακολουθίας.

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

Οι τυπωμένες υποακολουθίες θα πρέπει να είναι αυξανόμενες, ασύνδετες και να έχουν το ίδιο μήκος - το μήκος της μεγαλύτερης αυξανόμενης υποακολουθίας.

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

Βαθμολογία

Σε κάθε υποπρόβλημα, ισχύει ότι ~1 \le n \le 1\,000\,000~.

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	10	~1 \le n \le 15~
2	40	~1 \le n \le 1000~
3	60	~1 \le n \le 1\,000\,000~

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

input

3
1 2 3

output

1 3
1 2 3

input

4
4 3 2 1

output

4 1
1
2
3
4

input

7
2 1 6 5 7 3 4

output

2 3
1 3 5
2 6 7

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

Το μήκος της μεγαλύτερης αυξανόμενης υποακολουθίας είναι 3. Η υποακολουθία που καθορίζεται από τους δείκτες 1, 3 και 5 (ή, τιμές 2, 6 και 7) αυξάνεται. Η υποακολουθία που καθορίζεται από τους δείκτες 2, 6 και 7 (ή, τιμές 1, 3 και 4) είναι επίσης αυξανόμενη. Οι δύο υποακολουθίες δεν έχουν κοινά στοιχεία και έχουν επίσης μέγιστο μήκος, γι' αυτό είναι μια έγκυρη επιλογή. Δεν είναι δυνατόν να επιλέξετε περισσότερες από δύο τέτοιες υποακολουθίες.