Empodija

UŽDUOTIS

Senovės graikų matematikas ir filosofas Pytagoras buvo įsitikinęs tikrovės matematine kilme. Šių dienų biologai nagrinėja biosekų savybes. Bioseka vadinama M sveikųjų skaičių seka, 
•	kurioje yra visi šie skaičiai: 0,1,…,M-1,
•	kuri prasideda 0 ir baigiasi M-1, 
•	kuri neturi tokių dviejų narių E, E+1 (t.y. esančių šia tvarka gretimose pozicijose)
Ištisinis biosekos posekis vadinamas atkarpa.

Biosekos atkarpa vadinama įrėmintu intervalu, jei pirmasis atkarpos elementas yra mažiausias iš atkarpos elementų, o paskutinysis – didžiausias ir nelygus pirmajam, o atkarpą sudaro visi sveikieji skaičiai nuo pirmojo iki paskutiniojo elemento imtinai. Įrėmintas intevalas vadinamas empodija, jeigu jame nėra jokio kito trumpesnio įrėminto intervalo.

Panagrinėkime bioseką (0,3,5,4,6,2,1,7). Ši seka sudaro sudaro įrėmintą intervalą. Tačiau joje yra kitas įrėmintas intervalas (3,5,4,6), taigi ši seka nėra empodija. Įrėmintame intervale (3,5,4,6) nėra trumpesnio įrėminto intervalo, taigi jis yra empodija. Tai yra vienintelė empodija šioje biosekoje. 

Parašykite programą, kuri pagal duotą bioseką rastų visas empodijas toje sekoje.

PRADINIAI DUOMENYS

Pradiniai duomenys įrašyti byloje empodia.in. Pirmoje eilutėje įrašytas vienas sveikasis skaičius M. Jis rodo, kiek sveikųjų skaičių sudaro bioseką. Tolesnėse M eilučių eilės tvarka įrašyti bioseką sudarantys skaičiai. Kiekvienoje šių M eilučių įrašytas vienas sveikasis skaičius. 

REZULTATAI

Rezultatų bylą pavadinkite empodia.out. Pirmoje bylos eilutėje įrašykite vieną sveikąjį skaičių H: biosekoje rastų empodijų skaičių. Tolesnės H eilučių apibūdina visas rastąsias empodijas. Empodijos pateikiamos ta tvarka kokia jos randamos, t. y. jei empodijos pradžia yra arčiau biosekos pradžios, ji anksčiau aprašoma. Kiekvienoje šių eilučių reikia įrašyti du tarpu atskirtus sveikuosius skaičius A ir B (pirma A, paskui – B); čia A-asis biosekos (pradiniuose duomenyse) elementas yra pirmasis empodijos elementas, o B-asis biosekos elementas – paskutinis empodijos elementas. 

PAVYZDŽIAI

empodia.in						empodia.out

8
0
3
5
4
6
2
1
7

1
2 5

RIBOJIMAI

Vienam testui galioja: 1000000≤M≤1100000.
Visiems kitiems testams galioja: 1≤M≤60000. 
50% testų galioja M≤2600.