Poklon

Ο μικρός Mirko είναι ένας πολύ απλός άνθρωπος. Ο φίλος του Mirko, ο Darko, του έδωσε έναν πίνακα με ~N~ φυσικούς ακέραιους και του ρώτησε ~Q~ ερωτήματα σχετικά με τον πίνακα που πρέπει να απαντήσει ο Mirko.
Κάθε ερώτημα αποτελείται από δύο ακέραιους αριθμούς, τις θέσεις του αριστερού και του δεξιού άκρου ενός διαστήματος στον πίνακα. Η απάντηση στο ερώτημα είναι ο αριθμός των διαφορετικών τιμών που εμφανίζονται ακριβώς δύο φορές στο δεδομένο διάστημα.

Είσοδος

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

Έξοδος

Η έξοδος πρέπει να αποτελείται από ~Q~ γραμμές, κάθε γραμμή να περιέχει την απάντηση σε ένα ερώτημα, αντίστοιχα.

Βαθμολογία

Σε περιπτώσεις δοκιμών αξίας 56 βαθμών συνολικά, οι αριθμοί ~N~ και ~Q~ δεν θα είναι μεγαλύτεροι από ~5\,000~.

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

input

5 1
1 2 1 1 1
1 3

output

1

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

Στο διάστημα από το πρώτο έως το τρίτο στοιχείο, υπάρχει μόνο ένας αριθμός (αριθμός 1) που εμφανίζεται ακριβώς δύο φορές.

input

5 2
1 1 1 1 1
2 4
2 3

output

0
1

input

5 2
1 1 2 2 3
1 1
1 5

output

0
2