Index

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

Ο Μίρκο πλησιάζει στη σύνταξη. Στη ζωή του είχε δημοσιεύσει ~n~ εργασίες και τώρα αναρωτιέται ~q~ φορές το εξής: "Αναρωτιέμαι, ποιος θα ήταν ο h-index μου αν είχα δημοσιεύσει μόνο τα ~l_i~ έως ~r_i~ άρθρα;"

Βοηθήστε τον να υπολογίσει τις απαντήσεις.

Είσοδος

Η πρώτη γραμμή περιέχει ακέραιους αριθμούς ~n~ και ~q\;(1 \le n, q \le 200\,000)~, τον αριθμό των άρθρων και τον αριθμό των ερωτήσεων.

Η δεύτερη γραμμή περιέχει ~n~ ακέραιους αριθμούς ~p_i\;(1 \le p_i \le 200\,000)~, όπου ~p_i~ είναι ο αριθμός των παραπομπών της ~i~-οστής εργασίας.

Οι ακόλουθες γραμμές ~q~ περιέχουν η καθεμία δύο ακέραιους αριθμούς ~l_i~ και ~r_i\;(1 \le l_i \le r_i \le n)~, τα τελικά σημεία της ~i~-οστής ερώτησης.

Έξοδος

Εξάγετε ~q~ γραμμές. Στην ~i~-οστή γραμμή εξόδου η απάντηση που δίνεται είναι για την ~i~-οστή ερώτηση.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	20	~1 \le n, q \le 1000~
2	40	~1 \le n, q \le 50\,000~
3	50	Κανένας επιπλέον περιορισμός.

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

input

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

output

1
3
3
1
2
2