Module: Algoritmo Mo

Problem

Ti viene fornito un array di numeri interi A di lunghezza n.
È necessario rispondere a m interrogazioni della forma "riportare il numero di numeri diversi di un sottosegmento dell'array A dall'elemento con indice l all'elemento con indice r" (entrambi i limiti del sottosegmento sono inclusi, l'array è numerato a partire da uno).

Inserimento:
La prima riga contiene due numeri: n - il numero di elementi dell'array e m - il numero di richieste (1 <= n, m <= 10⁵).
La seconda riga contiene n numeri interi A_i - elementi dell'array (0 <= A_i <= 10⁶).
Poi ci sono m righe, ciascuna contenente due numeri l e r - i confini del sottosegmento per ogni query (1 <= l <= r <= n).

Uscita:
In una singola riga stampa m numeri separati da spazio: per ogni query, il numero di numeri diversi nel sottosegmento corrispondente.

Esempio:
 

Input	Uscita
7 5 1 3 1 2 2 4 1 1 3 4 5 37 24 77	2 1 3 3 1