Hop

                                                    ♪ Jeremiah was a bullfrog
                                                   Was a good friend of mine ♪

Υπάρχουν n νούφαρα, αριθμημένα από το 1 έως το ~n~, σε μια γραμμή. Στο ~i~-οστό νούφαρο υπάρχει ένας θετικός ακέραιος ~x_i~ και η ακολουθία ~(x_i)_{1 \le i \le n}~ είναι αυστηρά αύξουσα.

Εισάγετε τρία βατράχια.

Κάθε ζευγάρι από νούφαρα ~(a,\;b)~, όπου ~a < b~, πρέπει να ανήκει στον βάτραχο 1, στον βάτραχο 2 ή στον βάτραχο 3.

Ένας βάτραχος μπορεί να πηδήξει από το νούφαρο ~i~ στο νούφαρο ~j > i~, αν το ζεύγος ~(i,\;j)~ ανήκει σε αυτό και το ~x_i~ διαιρεί το ~x_j~.

Μοιράστε τα ζεύγη μεταξύ των βατράχων έτσι ώστε κανένας βάτραχος να μην μπορεί να κάνει περισσότερα από 3 συνεχόμενα άλματα.

Είσοδος

Η πρώτη γραμμή περιέχει έναν θετικό ακέραιο ~n\;(1 \le n \le 1000)~, τον αριθμό των νούφαρων.

Η δεύτερη γραμμή περιέχει ~n~ θετικούς ακέραιους ~x_i\;(1 \le x_i \le 1018)~, τους αριθμούς των νούφαρων.

Έξοδος

Αποτελείται από ~n - 1~ γραμμές. Στην i-οστή γραμμή τυπώνουμε ~i~ αριθμούς, όπου ο ~j~-οστός αριθμός είναι το νούμερο του βατράχου στον οποίο ανήκει το ~(j,\;i+1)~.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	10	~n \le 30~
2	100	Κανένας επιπλέον περιορισμός.

Εάν στη λύση σας κάποιος βάτραχος μπορεί να κάνει ~k~ διαδοχικά άλματα, όπου ~k > 3~, αλλά κανένας βάτραχος δεν μπορεί να κάνει ~k + 1~ διαδοχικά άλματα, η βαθμολογία σας για αυτήν την περίπτωση δοκιμής είναι ~f(k) \cdot x~ πόντοι, όπου:

$$\displaystyle f(k) = \frac{1}{10} \cdot \begin{cases} 11 - k, & \text{αν } & 4 \leq k\le 5 \\ 8-[k/2] & \text{αν } & 6 \le k \le 11 \\ 1 & \text{αν } & 12 \le k \le 19 \\ 0 & \text{αν } & k \ge 20. \end{cases}$$

και ~x~ είναι ο αριθμός των σημείων γι' αυτό το υποπρόβλημα.

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

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

input

8
3 4 6 9 12 18 36 72

output

1
2 3
1 2 3
1 2 3 1
2 3 1 2 3
1 2 3 1 2 3
1 2 3 1 2 3 1

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

Οι βάτραχοι σημειώνονται ως εξής: με μπλε (1), με πράσινο (2) και με κόκκινο (3).

Ο μπλε βάτραχος μπορεί να πηδήξει από το νούφαρο ~x_1 = 3~ στο νούφαρο ~x_4 = 9~, μετά στο νούφαρο ~x_7 = 36~ και μετά στο ~x_8 = 72~. Αυτοί είναι τα μόνα τρία συνεχόμενα άλματα που μπορεί να κάνει κάθε βάτραχος.

Ο πράσινος βάτραχος μπορεί να πηδήξει από το νούφαρο ~x_2 = 4~ στο νούφαρο ~x_5 = 12~ και μετά στο ~x_7 = 36~, επειδή το 4 διαιρεί το 12 και το 12 διαιρεί το 36. Αυτά είναι δύο διαδοχικά άλματα.

Ο κόκκινος βάτραχος δεν μπορεί να πηδήξει από το νούφαρο ~x_2 = 4~ στο νούφαρο ~x_3 = 6~, γιατί το 6 δεν διαιρείται ακριβώς με το 4.

Κανένας βάτραχος δεν μπορεί να κάνει περισσότερα από τρία συνεχόμενα άλματα.

input

2
10 101

output

1