Ograda

Στο χωριό του Mirko όλοι οι φράχτες είναι κατασκευασμένοι από ακριβώς ${\rm N}$ σανίδες με διαφορετικά ύψη. Ο Mirko δεν έχει ακόμη δικό του φράχτη, οπότε αποφάσισε να χτίσει έναν.
Κάθε πίνακας αντιπροσωπεύεται από έναν θετικό ακέραιο μικρότερο από ${10}^9$ - το ύψος του. Ορίζουμε την ομορφιά του φράχτη ως το άθροισμα των υψομετρικών διαφορών μεταξύ των παρακείμενων σανίδων.
Ο Mirko αγόρασε ήδη τις σανίδες, αλλά δεν ξέρει πώς να τις ταξινομήσει σε φράχτη. Θα ήθελε ο φράκτης του να είναι παρόμοιος με τον φράκτη του Slavko, αλλά και να είναι όσο πιο ωραίος γίνεται.
Λέμε ότι δύο φράκτες είναι όμοιοι εάν η σειρά των παρακείμενων σανίδων είναι ίδια και στους δύο φράχτες, δηλαδή εάν η $i$-οστή σανίδα ενός φράχτη είναι μικρότερη (ή μεγαλύτερη) από την $(i+1)$-οστή, τότε πρέπει να ισχύει το ίδιο και για αυτό σανίδες του άλλου φράχτη.
Δεδομένης της διαμόρφωσης του φράχτη του Slavko και των υψών των σανίδων που αγόρασε ο Mirko, συνέθεσε τον φράκτη του Mirko έτσι ώστε να είναι παρόμοιος με αυτόν του Slavko αλλά και όσο το δυνατόν πιο ωραίος. Εάν υπάρχουν περισσότερες από μία λύσεις, εξάγετε οποιαδήποτε από αυτές.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει ακέραιο αριθμό $N(2\le N\le 300000)$, αριθμό πινάκων σε κάθε φράχτη.
Η ακόλουθη γραμμή περιέχει $N$ διαφορετικούς θετικούς ακέραιους που αντιπροσωπεύουν το φράχτη του Slavko.
Η ακόλουθη γραμμή περιέχει $N$ διαφορετικούς θετικούς ακέραιους που αντιπροσωπεύουν τα ύψη των σανίδων που αγόρασε ο Mirko για τον φράχτη του.

Έξοδος

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

Βαθμολογία

Το $50$% των πόντων για την περίπτωση δοκιμής θα απονεμηθεί εάν η ομορφιά είναι σωστή, αλλά η δεύτερη γραμμή είναι λανθασμένη ή δεν βγαίνει καθόλου.

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

input

4
5 7 4 9
1 2 3 4

output

7
2 4 1 3

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

Ο Mirko αγόρασε σανίδες των υψών 1, 2, 3 και 4. Οι φράχτες παρόμοιοι με εκείνους του Slavko που μπορεί να χτίσει είναι:

input

10
9 5 1 2 6 7 4 18 20 12
10 40 20 30 50 70 80 100 1000 500

output

3010
100 80 10 40 50 1000 20 70 500 30