Республиканская олимпиада по информатике, 2011 год, 9 класс

Есеп D. Бiрегей сандар

Ограничение по времени:

2 секунды

Ограничение по памяти:

256 мегабайта

Сiзге ұзындығы $N$-ға тең, бүтiн сандар $A$ массивi және осы массивтiң $[l, r]$ ретiнде көрсетiлетiн $M$ интервалдар берiледi. Әр интервал үшiн $A[l],$ $A[l + 1],$ $\ldots,$ $A[r]$ арасындағы әр түрлi сандардың санын табыңыз.

Формат входного файла

Енгiзу файлдың бiрiншi жолында екi бүтiн сандар $N$ және $M$ берiледi $(1 \le N \le 10^5,$ $1 \le M \le 10^5).$ Келесi жолда $A$ массивi жазылған: $N$ бүтiн сандар $A[i]$ $(1 \le A[i] \le 10^9).$ Келесi $M$ жолдың әрқайсысында екi сандар $l[i]$ және $r[i]$ $(1 \le l[i] \le r[i] \le N)$ — сәйкес интервалдың ұштары берiледi.

Формат выходного файла

Шығыс файлда $M$ жолдар болуы тиiс. $i$-шi жолда $A$ массивiнiң енгiзу файлдың $(i+3)$-шi жолында берiлген, интервалда әр түрлi сандардың санын тауып шығарыңыз.

Примеры:

Вход

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

Ответ

2
2
2
3
3
3