Doktor

Και η δεσποινίδα, κυρία, λέει: "Καβαλάω άλογα για δεκαπέντε χρόνια, και είναι αδύνατο να πεταλώσω ένα άλογο ανάποδα!"(...) ~(\ldots)~

"Ναι, αυτό είναι ανάποδα" - ψιθυρίζει ο Domagoj, κοιτάζοντας το χέρι του Mate ενώ παίζει, για τους σκοπούς αυτής της εργασίας, μια πολύ τροποποιημένη έκδοση του παιχνιδιού με κάρτες Hanabi. Για λόγους απλότητας, ο Mate κρατά στα χέρια του ~N~ φύλλα, αριθμημένα κατά ~1,\;2,\;\ldots,\;N~ με συγκεκριμένη σειρά. (Κάθε αριθμός από το 1 έως το ~N~ εμφανίζεται ακριβώς μία φορά). Όπως όταν παίζει το πραγματικό παιχνίδι, δεν μπορεί να αλλάξει οικειοθελώς τη σειρά της κάρτας.

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

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

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

Βοηθήστε τον Domagoj να ανακαλύψει ποια συνεχόμενη υπακολουθία πρέπει να επισημάνει, έτσι ώστε ο αριθμός των σταθερών σημείων στο χέρι του Mate μετά την περιστροφή αυτής της υπακολουθίας να είναι ο μέγιστος.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τον θετικό ακέραιο αριθμό ~N\;(1 \le N \le 500\,000)~, τον αριθμό των φύλλων στο χέρι του Mate.
Η ακόλουθη γραμμή περιέχει τους αριθμούς στις κάρτες στο χέρι του Mate με τη σειρά που τους βλέπει ο Domagoj.

Έξοδος

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

Βαθμολογία

Σε δοκιμαστικές περιπτώσεις αξίας 30% των συνολικών πόντων, θα ισχύει ~N \le 500~.
Σε δοκιμαστικές περιπτώσεις αξίας επιπλέον 30% των συνολικών πόντων, θα ισχύει ~N \le 5\,000~.

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

input

4
3 2 1 4

output

3 1

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

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

input

2
1 2

output

1 1

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

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

input

7
3 6 5 7 4 1 2

output

3 2