B. Бяцхан дээрэмчин охины амьтны хүрээлэн

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Бяцхан дээрэмчин охин хөгжилдөхийн тулд өөрийн амьтны хүрээлэн дахь амьтдыг айлгах дуртай. Тэр амьтдыг өндрийнх нь өсөх дарааллаар нэг мөрөнд жагсаахаар шийдсэн. Гэсэн ч амьтад зөв газартаа зогсож чадахааргүйгээр маш их айсан байсан.

Дээрэмчин охин эхэндээ ууртай байсан боловч амьтдыг өөрөө жагсаахаар шийдсэн. Тэр давталттайгаар $r - l + 1$ нь тэгш байх $l$ ба $r$ тоонуудыг нэрлэнэ. Үүний дараа $l$ болон $r$-ийг оруулаад энэ хоорондох байрлалыг эзлэж байгаа амьтад дараах байдлаар дахин байрлана: $l$ байрлалд байгаа амьтан $l + 1$ байрлалд байгаа амьтантай солигдоно, $l + 2$ байрлалд байгаа амьтан $l + 3$ байрлалд байгаа амьтантай солигдоно, ..., эцэст нь $r - 1$ байрлалд байгаа амьтан $r$ байрлалд байгаа амьтантай солигдоно.

Дээрэмчин охинд амьтдыг өндрийнх нь өсөх дарааллаар байрлуулахад нь туслана уу. Та хамгийн ихдээ $20 000$ сегмент нэрлэж болно, учир нь үүнээс их бол дээрэмчин охин уйдах ба дахин амьтдыг айлгаж эхлэнэ.

Оролт

Эхний мөрөнд нэг бүхэл тоон утга $n$ ($1 ≤ n ≤ 100$) байх буюу дээрэмчин охины амьтны хүрээлэн дахь амьтдын тоо юм.

Хоёр дахь мөрөнд зайгаар тусгаарлагдсан $n$ бүхэл тоон утга $a_{1}, a_{2}, ..., a_{n}$ ($1 ≤ a_{i} ≤ 10^{9}$) байх ба энд $a_{i}$ нь $i$-р байрлалыг эзэлж буй амьтны өндөр юм.

Гаралт

Амьтдыг өндрөөр нь өсөх дарааллаар жагсаах үйлдлүүдийн дарааллыг хэвлэ.

Гаралтанд хэд хэдэн мөр байх ба $i$-р мөрөнд зайгаар тусгаарлагдсан хоёр бүхэл тоон утга $l_{i}$ ба $r_{i}$ ($1 ≤ l_{i} < r_{i} ≤ n$) байх ба эдгээр тоонууд нь дээрэмчин охины нэрлэх ёстой сегментүүдийн тайлбар юм. Сегментүүдийг хийгдэх үйлдлийнх нь дарааллаар тодорхойлох ёстой.

Үйлдлүүдийн тоо нь $20 000$-с хэтрэхгүй байна.

Хэрвээ амьтад нь анхнаасаа зөв эрэмбэлэгдсэн байвал та ямар ч гаралт хэвлэхгүй байж болно.

Орчуулсан: Г.Мэндбаяр

Жишээ тэстүүд

Оролт
4
2 1 4 3
Гаралт
1 4
Оролт
7
36 28 57 39 66 69 68
Гаралт
1 4
6 7
Оролт
5
1 2 1 2 1
Гаралт
2 5
3 4
1 4
1 4

Тэмдэглэл

Та үйлдлүүдийн тоог хамгийн бага байлгах шаардлагагүй. $20 000$-с бага үйлдэлтэй бол ямар ч шийдэл зөвд тооцогдоно.

Сэтгэгдлүүдийг ачааллаж байна...