Prokletnik

Ο νεαρός Luka πρόκειται να μπει σε ένα σπίτι με την κακιά μάγισσα Μαρίκα μέσα. Μόλις μπαίνει στο σπίτι, του κάνει ερωτήσεις σχετικά με τον πίνακα των \(Ν\) αριθμών της. Ο Luka έντρομος ζητά διευκρίνιση των ερωτήσεων. Η Marica του εξηγεί ότι κάθε ερώτημα αποτελείται από δύο ακέραιους ~L~ και ~R~ που αντιπροσωπεύουν τις θέσεις ενός συνεχόμενου υπο-πίνακα στον πίνακα της.

Είναι καθήκον του Luka να απαντήσει για κάθε ερώτημα ποιός είναι ο μεγαλύτερος συνεχόμενος υπο-πίνακας αυτού του συνεχόμενου υπο-πίνακα (μπορεί να είναι ολόκληρος ο υπο-πίνακας) που έχει την ιδιότητα να είναι μαγικός. Ένας πίνακας ονομάζεται μαγικός εάν όλες οι τιμές βρίσκονται μεταξύ των τιμών του πρώτου και του τελευταίου αριθμού σε αυτόν τον πίνακα. Για παράδειγμα, το ~[1\;3\;1\;2\;4]~ είναι μαγικό, το ίδιο με το ~[4\;1\;1\;2\;1]~, ενώ το ~[3\;3\;4\;1]~ δεν είναι μαγικό.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τον ακέραιο αριθμό ~N\;(1 \leq N \leq 500\,000)~, τον αριθμό των αριθμών στον πίνακα.
Η δεύτερη γραμμή περιέχει ~N~ ακέραιους αριθμούς ~a_i\;(1 \leq a_i \leq 10^9)~.
Η τρίτη γραμμή περιέχει τον ακέραιο ~Q\;(1 \leq Q \leq 500\,000)~, τον αριθμό των ερωτημάτων.
Κάθε μία από τις ακόλουθες γραμμές ~Q~ περιέχει δύο ακέραιους αριθμούς, ~L~ και ~R\;(1 \leq L \leq R \leq N)~, που αντιπροσωπεύουν τον υπο-πίνακα από το ερώτημα.

Έξοδος

Η ~i~-οστή γραμμή εξόδου πρέπει να περιέχει έναν μόνο ακέραιο αριθμό - την απάντηση στο ~i~-οστό ερώτημα.

Βαθμολογία

Σε περιπτώσεις δοκιμής αξίας ~50~% των συνολικών πόντων, θα ισχύει ~N,\;Q \leq 30\,000~.

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

input

5
5 4 3 3 2
3
1 2
1 1
2 4

output

2
1
3

input

6
6 6 5 1 6 2
3
4 5
4 6
1 4

output

2
2
4