Nosaukums
Gudrie sienāži (gusi)
Laika limits
1.00s
Atmiņas limits
64.0 MB
Grūtība
13%

Definīcija

Gudrinieku ciemā dzīvo n gudri sienāži (sanumurēti ar skaitļiem no 0 līdz - 1), kas dienas sākumā atrodas uz koordināšu taisnes. Visi sienāži atrodas veselās koordinātēs no 0 līdz - 1, pie tam nekādi divi sienāži neatrodas vienā vietā. Sienāži pa nakti ir noguruši no lēkāšanas; i-tais sienāzis tagad ar vienu lēcienu var palekties garumā tieši i pa kreisi vai pa labi (ievērojiet, ka tas nozīmē, ka 0-tais sienāzis ir tik noguris, ka aizmiga un jau vairs nekustēsies). Pirms gulēšanas sienāži grib sakārtoties tā, lai katriem diviem sienāžiem, sienāzis ar mazāku numuru atrastos stingri pa kreisi no sienāža ar lielāko numuru. Ievērojiet, ka diviem secīgiem sienāžiem beigās nav obligāti jābūt tieši blakus viens otram. Kārtošanas procesā vairāki sienāži var atrasties vienā vietā.

Sienāži negrib daudz piepūlēties pirms gūlētiešanas, tāpēc Jums ir jānoskaidro, kāds ir mazākais kopējais lēcienu skaits, kas sienāžiem ir jāizpilda, lai to secība būtu pareiza! 


Ievaddatu raksturojums

Pirmajā rindā dots naturāls skaitlis n (1 ≤ n ≤ 2000). Nākamajā rindā doti n veseli skaitļi x0, x1, ..., x- 1, kas apzīmē sākotnējās sienāžu koordinātes (0 ≤ xi- 1).


Izvaddatu raksturojums

Izvadiet vienu veselu skaitli – mazāko iespējamo lēcienu skaitu, lai sienāži varētu sakārtoties pareizā secībā.


Piezīmes

Uzdevumā var iegūt daļējus punktus:

  • 1 ≤ n ≤ 10 dod 20% punktu;
  • 10 < n ≤ 50 dod 20% punktu;
  • 50 < n ≤ 2000 dod 60% punktu.

Paraugdati

Stdin
5
1 0 4 2 3
Stdout
4

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.