Poklon

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

Είσοδος

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

Έξοδος

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

Βαθμολογία

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

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

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