Напомена: ово је незванична копија задатака. Као таква, не гарантује се да ће овај сајт бити одржаван, и немојте се изненадити ако са њега задаци одједном нестану.
У ово време глобалне епидемије вируса, наш познати научник Милош је, као једини довољно квалификовани научник за овај посао, добио задатак да анализира генетску структуру вируса у својој лабараторији. Ако његова анализа буде успешна, она ће загарантовати проналажење лека и ослобођење света од вируса.
Генетска структура вируса \(G\) се може представити као пермутација бројева од \(1\) до \(N\), то јест, низ бројева од \(1\) до \(N\) дужине \(N\) где се сваки број појављује тачно једном.
Како би Милош могао да уради своју анализу, генетска структура мора да буде сортирана. За соритрање генетске структуре, Милош користи веома специјалну машину. Ова машина му дозвољава да узме неки сегмент низа и обрне га. Тачније, може да одабере два индекса \(l\) и \(r\) тако да важи \(l\leq r\), и обрне подниз од \(l\)-те до \(r\)-те позиције у низу (замени места елементима \(G_l\) i \(G_r\), \(G_{l+1}\) i \(G_{r-1}\), \(\ldots\) ). Милош такође зна да су гени веома осетљиви и да ће се оштетити ако употреби машину више пута на исти ген (Милош може да употреби машину произвољан број пута, али интервали индекса које одабере морају бити дисјунктни).
Како Милош нема искуства са коришћењем ове машине, потребна му је ваша помоћ! Кажите му да ли је могуће уз помоћ ове машине сортирати генетску структуру без оштећења гена или не. Ако је сортирање генетске структуре могуће, такоће му је потребна и секвенца операција коју треба применити ради успешног сортирања. Због тога што је машина спора, а Милош хоће да лек буде готов што пре, потребно је и да секвенца операција буде најкраћа могућа (уколико постоји више најкраћих секвенци, исписати било коју).
Прва линија стандардног улаза садржи број \(N\), дужину генетске структуре. Друга линија стандардног улаза садржи низ \(G\), генетску структуру.
Уколико је сортирање генетске структуре могуће, у првој линији стандардног излаза исписати “Svet je spasen”, у другој линији стандардног излаза исписати дужину најкраће могуће секвенце операција \(K\). У свакој од наредних \(K\) линија исписати два броја \(l_i\) и \(r_i\), индексе које Милош треба да одабере за \(i\)-ту операцију. Уколико сортирање генетске структуре није могуће, у првој и јединој линији стандардног излаза исписати “Nema spasa”
8
2 1 4 3 5 6 7 8Svet je spasen
2
1 2
3 48
1 6 7 3 2 5 4 8Nema spasaТест примери су подељени у 5 подзадатка: - [10 поена]: \(N \leq 3\) - [20 поена]: \(N \leq 20\) - [30 поена]: Ако постоји, најкраћа секвенца операција је дужине \(0\) или \(1\), \(N \leq 500\) - [20 поена]: \(N \leq 500\) - [20 поена]: Нема додатних ограничења