Enciklopēdiju sējumu kārtošana - 2

ID: sejumi2
Grūtība: 2/5
Laika limits: 1

Uzdevums

Bibliotēkas izziņu grāmatu sekcijā ir enciklopēdija, kurai ir N sējumi, kas numurēti pēc kārtas ar skaitļiem no 1 līdz N. Katru dienu cilvēki šos sējumus lieto, tādēļ dienas beigās tie bieži vien plauktā neatrodas pareizajā secībā (sakārtoti numuru pieaugšanas secībā no kreisās uz labo pusi).
Jūsu uzdevums ir uzrakstīt programmu, kas bibliotekāram palīdz plauktā atjaunot pareizo sējumu secību.
Sējumu sakārtošanai ir atļautas diva veida operācijas -

  1. bibliotekārs paņem vienu sējumu no plaukta, pabīda visus pa labi palikušos sējumus pa kreisi un pēc tam paņemto sējumu novieto sējumu rindas labajā galā. Šo operāciju sauc par "sējuma pabīdīšanu pa labi".
  2. bibliotekārs paņem vienu sējumu no plaukta, pabīda visus pa kreisi palikušos sējumus pa labi un pēc tam paņemto sējumu novieto sējumu rindas kreisajā galā. Šo operāciju sauc par "sējuma pabīdīšanu pa kreisi".

Piemēram, ja sējumi ir sakārtoti secībā
1 3 2 4 5
, tad pēc 2.sējuma pārbīdīšanas pa labi sējumu secība būtu
1 3 4 5 2
, un tālāk pēc 4.sējuma pabīdīšanas pa kreisi, sējumu secība būtu
4 1 3 5 2

Programmai katram dotajam enciklopēdijas sējumu sakārtojumam jānosaka mazākais sējumu skaits, kādu nepieciešams pārbīdīt, lai sējumi plauktā atkal būtu pareizajā secībā.

 

Ievaddati

Teksta faila sejumi.in pirmajā rindā dots naturāls skaitlis N - sējumu skaits (N<=20000). Faila otrajā rindā doti N skaitļi - sējumu numuri tādā secībā, kādā tie atrodas plauktā. Starp katriem diviem blakus skaitļiem failā ir viens tukšumsimbols.

 

Izvaddati

Teksta faila sejumi.out vienīgajā rindā jāizvada viens vesels skaitlis - mazākais pārbīdāmo sējumu skaits, lai iegūtu pareizu sējumu secību.

 

Piemērs

sejumi.insejumi.out
4
1 4 2 3
1
  
sejumi.insejumi.out
5
1 2 3 4 5
0

 

Atsauces

Autors: Mārtiņš Opmanis
© 2001-2002 olimps! http://www.lio.lv/olimps/