DER UNTERGANG - 狗狗也要光榮地死去

題目敘述

費格萊茵被帶到了地堡外，「站住」費格萊茵緩緩地轉過頭，看到面前的士兵正在幫他的機關槍裝子彈，他趕忙將扣子扣好，大喊一聲「希特勒萬歲(茶葉蛋)」就立馬被掃射而死。

地堡中，最後的追隨者都在想怎麼和元首一起殉國。洪普斯睡不著覺，再前往餐廳的路上剛好遇上元首，「休息的好嗎？」元首親切地打招呼，元首叫洪普斯打開他的打字機，「我的政治遺囑：從我1914年作為一名志願兵參加一戰，為國效力到現在已經30多年了。在這30年我的思考、行動和生活中，只有對人民的熱愛和忠誠讓我感動。......時間會流逝，但是在我們城市和紀念碑的廢墟上，對那些對我們犯下滔天罪刑的人的仇恨將時刻不忘，國際猶太教和他的同盟們。」

元首離開後，戈培爾哭著走進洪普斯的工作室，「怎麼了？部長閣下」小黃關上了門「你想想看，元首要我離開柏林，他下的命令。我從未違抗過元首的命令」小黃擦了一下眼淚「但這次我不會服從，我會留下來陪著元首。求你了，瓊格夫人(是的，我們女主角有結婚)」戈培爾啜泣了一下「我想向你口述我的遺囑」「我正在打元首的遺囑」「好，我明白了，再說吧」小黃轉身離開。

此時元首找了一位牧師到地堡中「元首，按造種族法案我必須問您...元首，你是純正的雅利安人嗎？」「是的」「能讓我看您的證件嗎？」，「你正在跟元首說話」一旁的戈培爾忍不住開口了，「好吧」牧師轉向愛娃「您，布萊恩小姐，您是純正的雅利安人嗎？」「是的」「那就沒有什麼能阻止我們了。您，我的元首，阿道夫.希特勒，你願意娶這位愛娃.不勞恩做你的妻子嗎？請回答『願意』」「願意」「您，愛娃.布萊恩，願意嫁給我們的元首，阿道夫.希特勒嗎？請回答『願意』」「願意」，牧師揮了揮手「我宣布你們結為夫妻」，四周的人起身鼓掌。

外邊的戰況依然慘烈，蒙克將軍前往元首的休息室，「還能支持多久」元首問到「也許20小時，最多了，俄國人從四周已經逼近到幾百米了。目前我們迫使他們停了下來」，「聽著，蒙克，西方民主已經沒落，他們將臣服於東方人。很好，謝謝你，這不僅僅是為了德國」

蒙克走了以後元首接到了凱特爾來的電報，說明了溫克的軍隊已經被擋住了，元首所有的軍隊都被重重包圍，說明解圍已經無望了，「聽者普瑟，我和我的妻子會自殺，我不想我的屍體落到俄國人的手上，無論死活我都不想落到俄國人的上。我想立即火化不被任何人找到」元首摸了一下普瑟的胸部「普瑟，你保證...保證無論如合一定做到」「元首，這是一項可怕的命令，但是我會執行的」元首拍了拍普瑟的胸。

恩斯特.申克醫生正在和軍官們喝酒，他突然想上廁所，當他踏進廁所時看到元首的愛犬對著他凶狠的吼著，但是他不以為意繼續去上他的廁所。

當他上完廁所後，發現狗狗已經不見了，在走廊上看見元首正和一群人抓著狗狗正在做些什麼事情，「過來，布隆迪」一個軍官抓住布隆迪的嘴，哈澤醫生用夾子將氰化鉀膠囊塞進牠的嘴巴中，然後夾破，布隆迪痛苦的嗚嗚的叫，元首將臉轉向旁邊，用表情表達了言語無法表達的痛苦...

元首在第一次和洪普斯見面的時候，就有說過他的布隆迪比一些人類都還要聰明，甚至比斯大林聰明。他曾經幫布隆迪做過智力測驗，將$N$個的數字排成一排，然後問布隆迪$M$個問題，第$i$個問題會給你一個區間$[l_i,r_i]$，布隆迪會告訴元首這個區間有幾個不同的數字(用叫的)，現在布隆迪已經走了，你為了證明自己的智利不會比布隆迪低，你也打算來挑戰這個問題。

InputFile

有多筆測資，總共不會超過$20$比，每筆測試資料開始有一行兩個整數$N,M(1 \leq N,M \leq 10^5)$，接下來一行有$N$個整數$a_1,a_2,...,a_N(0 \leq a_i \leq 10^9)$，表示排成一排的數字。接下來$M$行，每行有兩個整數$l_i,r_i(1 \leq l_i \leq r_i \leq N)$，代表元首對布隆迪的詢問

OutputFile

輸出對於每個元首的詢問，區間$[l_i,r_i]$中有幾種不同的數字，各位應該都比布隆迪還聰明吧？

範例輸入

6 2
3 1 4 1 5 9
3 5
2 5
8 1
2 8 8 2 5 2 5 2
1 8

範例輸出

3
3
3

限制:

時限	1000ms
記憶體	6553500 bytes

Judge Setting

run-time limit: 1000 ms
memory limit: 6553500 byte
測資數量: 0