Mali Đurica je veliki obožavatelj knjiga i čvrsto je rešio da pročita što više knjiga u narednih godinu dana. Prvi, jelte, logičan korak je da ode u biblioteku i tamo potraži štivo za čitanje, što je Đurica i uradio. Radi pojednostavljenja, biblioteku ćemo zamisliti kao niz knjiga. Đurica smatra da će čitanje biti zanimljivije ako čita knjige različitih autora. Shodno tome, prva stvar koju je Đurica zaključio da mu je neophodna jeste da prebroji koliko različitih autora je učestvovalo u pisanju datog podniza uzastopnih knjiga.

Tu stupate vi. Baš vas je zamolio Đurica da mu pomognete i date odgovor na dato pitanje. Jedna olakšavajuća okolnost je to što za svaku knjigu važi da je pisao isključivo jedan autor. Umesto imena autora knjige, Đurica će vam dati jedinstveni broj autora, koji je u stvari broj iz intervala [1, 100 000]. Svaki autor ima tačno jedan jedinstveni broj, i svaki jedinstven broj odgovara tačno jednom autoru.

Ulaz.

(Ulazni podaci se učitavaju sa standardnog ulaza) U prvom redu nalaze se celi brojevi n (1 ≤ n ≤ 100:000) i K (1 ≤ K ≤ 100:000). U narednom redu se učitava n celih brojeva iz intervala [1, 100 000] koji redom predstavljaju jedinstvene brojeve autora knjiga datog niza. Potom se u K redova učitavaju redom indeksi idxs_i i idxe_i (idxs_i ≤ idxe_i, 1 ≤ i ≤ K) koji predstavljaju indeks početka i kraj podniza knjiga, redom, za koji treba odgovoriti koliko različitih autora je učestvovalo u pisanju knjiga tog podniza.

Izlaz.

(Izlazni podaci se ispisuju na standardni izlaz) U K redova ispisati odgovore na postavljena pitanja, u i-tom redu odgovor za podniz čiji su indeksi idxs_i i idxe_i iz ulaza.

Primer 1.

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

4
1
2
4
3
3

Primer 2.

4 3
1 1 12 12
1 4
1 2
3 4

2
1
1

Napomena.

• U 40% test primera jedinstveni brojevi autora će se kretati u intervalu [1, 60].
• U 30% test primera će i broj upita i broj različitih autora biti najviše 1000.
• U 60% test primera će biti ispunjen bar jedan od prethodna dva uslova.