Fişierul intrare/ieşire:valearegilor.in, valearegilor.outSursăConcursul National de Informatica "Adolescent Grigore Moisil" 18
AutorChichirim George, Vlad-Andrei MunteanuAdăugată deAGMinformaticaAGMInformatica AGMinformatica
Timp execuţie pe test2 secLimită de memorie262144 kbytes
Scorul tăuN/ADificultateN/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 [li, ri] al degetelor sale şi, cu fiecare întârziere, vor alege din acesta un deget pi+1 cu proprietatea că pi < pi+1 > pi+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 [li, ri], 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 p1 p2 ... pn. Urmează q linii descriind întrebările sub forma li ri.

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 ≤ liri ≤ n
  • Se va considera că degetele li-1 şi ri+1 au lungimea infinit în cadrul unei întrebări.

Exemplu

valearegilor.invalearegilor.out
15 4
1 2 3 4 5 10 8 6 7 9 14 13 11 12 15
1 5
3 3
10 14
4 15
5
1
3
8
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?