Fişierul intrare/ieşire:	valearegilor.in, valearegilor.out	Sursă	Concursul National de Informatica "Adolescent Grigore Moisil" 18
Autor	Chichirim George, Vlad-Andrei Munteanu	Adăugată de	AGMInformatica •AGMinformatica
Timp execuţie pe test	1 sec	Limită de memorie	262144 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Valea Regilor

Am pus cărămidă peste cărămidă
Până am ajuns sus pe piramidă

Mulţi dintre noi rămânem înmărmuriţi de măreţia singurei din cele Şapte minuni ale lumii antice care s-a păstrat peste vreme. Puţini suntem însă cei care ştiu cum au fost construite, de fapt, piramidele. Ultimele date istorice ne arată că pe vremea lui faraon se trăia într-o sărăcie lucie, rata şomajului fiind de 100%.
Întrebarea rămâne: de unde a avut totuşi faraon bani pentru a construi piramidele? De la cămătari, desigur (cei care făceau contrabandă cu probleme furate).

Zis şi făcut, faraon a împrumutat bani de la aceştia şi a construit cele mai înalte şi mai frumoase piramide din întreaga lume la acele timpuri, iar banii rămaşi i-a pierdut la păcănele, la Book of Ra desigur. Problema a urmat însă când a trebuit să înapoieze banii ...

Norocul face însă că faraon avea la mână n degete. Lungimile degetelor sale erau distincte două câte două şi formau o permutare.
Pe măsură ce deadline-ul se apropia, cămătarii l-au sunat pe faraon şi i-au transmis că dacă nu va înapoia banii vor alege un interval [l_i, r_i] al degetelor sale şi, cu fiecare întârziere, vor alege din acesta un deget p_i+1 cu proprietatea că p_i < p_i+1 > p_i+2 pe care îl vor tăia, până ce nu va mai exista un astfel de deget.

Speriat, faraon doreşte să afle răspunsul la q întrebări: Dacă ar fi ca cămătarii să aleagă intervalul [l_i, r_i], cu câte degete va mai rămâne în acest interval la final?

Date de intrare

Fişierul de intrare valearegilor.in conţine pe prima linie numerele n şi q. Pe următoarea linie se vor găsi lungimile degetelor sub formă de permutare p₁ p₂ ... p_n. Urmează q linii descriind întrebările sub forma l_i r_i.

Date de ieşire

În fişierul de ieşire valearegilor.out veţi afişa răspunsul la cele q întrebări ale lui faraon, câte unul pe linie.

Restricţii

• 1 ≤ n ≤ 100.000
• 1 ≤ q ≤ 1.000.000
• 1 ≤ l_i ≤ r_i ≤ n
• Se va considera că degetele l_i-1 şi r_i+1 au lungimea infinit în cadrul unei întrebări.

Exemplu

Cum se trimit solutii?