Као што знате, услед тренутне светске епидемиолошке ситуације, многобројни фестивали широм света су отказани. Међутим, постоји један фестивал, који се одржава сваке године у близини једног вама врло познатог градића у Русији, који је одлучио да се упркос свему ипак одржи. Како немате много избора који фестивал да посетите овог лета, одлучили сте да и ви постанете ове године учесник светски познатог Фестивала интервала.

На овом фестивалу свака атракција је представљена једним интервалом на бројевној прави. Због неке бизарне геометрије која се јавља у опскурним деловима Русије, знамо да су две атракције суседне ако и само ако је интервал који одговара једној од те две атракције подинтервал интервала који одговара другој од њих. Подсећамо вас да је интервал \([a,b]\) подинтервал интервала \([c,d]\) ако \(c\leq a\leq b\leq d\).

Ви не знате тачно како ћете се кретати по фестивалу, па вас за дате атракције \(u\) и \(v\) интересује најкраћи пут од атракције \(u\) до атракције \(v\), то јест, колико пута морате да путујете између суседних атракција да бисте стигли од атракције \(u\) до атракције \(v\). Веома сте узбуђени поводом вашег провода на фестивалу, па желите да сазнате одговор на претходно питање за чак \(Q\) различитих парова атракција \((u,v)\)!

Опис улаза

Прва линија стандардног улаза садржи два броја, број интервала \(N\), и број упита \(Q\). Друга линија стандардног улаза садржи низ \(A_i\) од \(2\cdot N\) бројева, по \(2\) појављивања сваког броја из скупа \(\{1,2,\ldots,N\}\), тако да индекс првог појављивања броја \(i\) у том низу представља почетак интервала \(i\), док индекс другог појављивања броја \(i\) у том низу представља крај интервала \(i\). У наредних \(Q\) линија стандардног улаза налазе се по два природна броја \(u_i,v_i\): индекси атракција између којих тражимо дужину најкраћег пута.

Опис излаза

На стандардни излаз испишите \(Q\) линија: у \(i\)-тој линији треба да пише одговор на \(i\)-ти упит.

Пример 1

Улаз

3 2
3 1 2 1 2 3
2 3
1 2

Излаз

1
2

Објашњење примера

Од \(2\) до \(3\) можемо да стигнемо директно, јер је интервал који одговара атракцији \(2\) подинтервал интервала који одговара атракцији \(3\). Атракције \(1\) и \(2\) нису суседне, па је најкраћи пут међу њима \(1-3-2\).

Ограничења

• \(1 \leq N,Q \leq 300.000\)
• \(1 \leq A_i \leq N\)
• Свака вредност од \(1\) до \(N\) се појављује тачно \(2\) пута у низу \(A_i\).
• \(1 \leq u_i,v_i \leq N\)
• \(u_i \neq v_i\)

Тест примери су подељени у 4 подзадатка:

• [18 поена]: \(N,Q\leq500\)
• [26 поена]: \(N,Q\leq3000\)
• [16 поена]: Свака два интервала су или дисјунктна, или је један подинтервал другог
• [40 поена]: Нема додатних ограничења