E. 3-н солилт

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

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

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

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

Морь үржүүлэгч Зениа-д нэг мөрөнд зогсож буй $n$ $(n > 1)$ морь байв. Морь болгон нь өөрийн гэсэн цорын ганц дугаартай. Анхандаа $i$-дахь морь нь $i$ дугаартай байв. Өөрөөр хэлбэл уг мөрөнд байгаа морьнуудын дугаарын дараалал нь дараах байдалтай харагдана (зүүнээс баруун уруу): 1, 2, 3, $...$, $n$.

Зениа тоглолтын өмнө морьнуудаа сургадаг. Сургуулилтын улирлын үеэр тэрээр морьнууддаа тушаалууд өгдөг. Тушаал бүр нь $l, r$ $(1 ≤ l < r ≤ n)$ гэсэн хос тоонууд байна. $l, r$ тушаал нь зүүнээсээ $l$-дах, $(l + 1)$-дэх, $(l + 2)$-дахь, $...$, $r$-дэх байрлалд байгаа морьнуудыг шинээр байрлуулах ёстой гэсэн үг юм. Ингэхдээ анхандаа $l$-дах болон $r$-дэх байрлалд зогсож буй морьнуудыг солино. $(l + 1)$-дэх болон $(r - 1)$-дэх байрлалд зогсож буй морьнуудыг солино. $(l + 2)$-дахь болон $(r - 2)$-дахь байрлалд зогсож буй морьнуудыг солино гэх мэтчилэн үргэлжилнэ. Өөрөөр хэлбэл $[l, r]$ сегмент дээр байх дарааллаар нь морьнуудыг урвуу морьтой нь солих юм.

Жишээлбэл Хэрэв Зениа $l = 2, r = 5$ гэсэн тушаал өгсөн ба морьнуудын дугаарын дараалал нь тушаалаас өмнө (2, 1, 3, 4, 5, 6) байсан бол уг тушаалын дараа (2, 5, 4, 3, 1, 6) болох юм.

Сургуулилтын үеэр Зениа өгөгдсөн хэлбэр бүхий хамгийн ихдээ 3-н тушаал өгдөг гэдгийг бид мэдэж байгаа. Танд сургуулилтын дараах морьнуудын дугаарын эцсийн дараалал өгөгдөв. Тэгвэл сургуулилтын үеэр Зениа-ын өгсөн тушаалуудыг олно уу. Та хариултандаа тушаалын тоог хамгийн бага байлгах хэрэггүй болохыг анхаарна уу. Хамгийн ихдээ 3-н тушаал агуулах боломжит хариултыг олно уу.

Оролт

Эхний мөрөнд уг морьнуудын тоо болох бүхэл тоо $n$ $(2 ≤ n ≤ 1000)$ өгөгдөнө. 2-дахь мөрөнд ялгаатай $n$ ширхэг бүхэл тоо $a_{1}, a_{2}, ..., a_{n}$ $(1 ≤ a_{i} ≤ n)$ өгөгдөх ба энд $a_{i}$ нь сургуулилтын дараах зүүнээсээ $i$-дахь морьны дугаар байна.

Гаралт

Эхний мөрөнд Зениа-ын сургуулилтын үеэр өгсөн тушаалын тоо $k$ $(0 ≤ k ≤ 3)$-г хэвлэнэ. Дараагийн $k$ мөрийн мөр болгонд 2 бүхэл тоо хэвлэнэ. $i$-дахь мөрөнд $l_{i}, r_{i}$ $(1 ≤ l_{i} < r_{i} ≤ n)$ тоонуудыг хэвлэх ба эдгээр нь Зениа-ын $i$-дахь тушаалыг илэрхийлнэ.

Нэг хариулт заавал оршин байна. Хэрэв олон тооны хариулт байвал та тэдгээрийн алийг нь ч хэвлэсэн болно.

Орчуулсан: Баатархүү

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

Оролт
5
1 4 3 2 5
Гаралт
1
2 4
Оролт
6
2 1 4 3 6 5
Гаралт
3
1 2
3 4
5 6
Сэтгэгдлүүдийг ачааллаж байна...