Алан \(p_1, p_2, \dots, p_n\) әр түрлі сандарымен жұмыс істейді. Оған \(q\) сұраныс \((L,R)\) берілген.

Бір сұраныс үшін Алан \(A = (p_L, p_{L+1}, \dots, p_R)\) массивін алады. Бастапқыда \(B\) массиві бос. Аланға келесі операцияны орындауға болады:

• \(k\) таңдау \((1 \le k \le |A|)\);

• \(A\) массивінен алғашқы \(k\) элементті жою;

• жойылған элементтерді \(B\) массивіне бір үздіксіз блок ретінде кез келген жерге (соның ішінде басына немесе соңына) орналастыру. Блок ішіндегі элементтердің тәртібін өзгертуге болмайды.

Операциялар \(A\) массиві бос болғанша (яғни барлық элементтер \(B\) массивіне көшірілгенше) орындалады.

\(cost(A)\) арқылы \(A\) массиві босатылғаннан кейін, соңғы \(B\) массивінің өспелі болуын қамтамасыз ету үшін қажетті минималды операциялар санын белгілейміз.

Әрбір \((L,R)\) сұранысы үшін Аланға \(cost(p_L, p_{L+1}, \dots, p_R)\) мәнін табуға көмектесіңіз.

Енгізу

Бірінші жолда екі бүтін сан \(n\) және \(q\) \((1 \le n, q \le 10^6)\) берілген.

Екінші жолда \(n\) бүтін саны \(p_1, p_2, \dots, p_n\) — \(1\)-ден \(n\)-ге дейінгі сандардың орыналмастырылуы.

Келесі \(q\) жолда екі бүтін сан \(L\) және \(R\) \((1 \le L \le R \le n)\) берілген.

Шығару

\(q\) жолды шығарыңыз. \(i\)-ші жолда \(i\)-ші сұраныс үшін жауапты шығарыңыз.

Мысалдар

Енгізу 1

8 4
3 4 5 1 2 8 6 7
1 8
4 6
3 4
7 7

Жауап 1

4
1
2
1

Ескертпелер

Бірінші сұраныс үшін \(L=1, R=8\) болғанда \(A=(3,4,5,1,2,8,6,7)\), ал \(B=\varnothing\). \(B\) массивін \(4\) операциямен сұрыптауға болады:

1. \((3,4,5)\) префиксін көшіргеннен кейін \(A=(1,2,8,6,7)\), \(B=(3,4,5)\) болады;

2. \((1,2)\) префиксін көшіріп, оны \(B\) массивінің басына орналастырғаннан кейін \(A=(8,6,7)\), \(B=(1,2,3,4,5)\) болады;

3. \((8)\) префиксін көшіргеннен кейін \(A=(6,7)\), \(B=(1,2,3,4,5,8)\) болады;

4. \((6,7)\) префиксін көшіріп, оны \(8\)-дің алдына орналастырғаннан кейін \(A=\varnothing\), \(B=(1,2,3,4,5,6,7,8)\) болады.

\(B\) массивін аз операциямен өспелі ету мүмкін емес екенін көрсетуге болады, сондықтан \(cost(A)=4\).