Uz bezgalīgi gara taisna sliežu ceļa vienādos attālumos viena no otras atrodas N lokomotīves. Katrai lokomotīvei ir unikāls numurs – naturāls skaitlis no 1 līdz N. Lokomotīves numurs norāda tās maksimālo kustības ātrumu kilometros stundā. Visas lokomotīves vienlaicīgi sāk kustēties uz priekšu (zīmējumā – pa labi) ar maksimālo iespējamo ātrumu. Ja kāda lokomotīve panāk priekšā braucošu lēnāku lokomotīvi, tā samazina kustības ātrumu un turpina braukt ar priekšā braucošās lokomotīves ātrumu. Pēc kāda laika visas lokomotīves ir sadalījušās grupās, kas turpmāk vairs nemainās.

Piemēram, sākumā sešas lokomotīves var būt izvietotas šādi:

Tad pēc kāda laika pēc kustības uzsākšanas tās sadalīsies trīs grupās, kas katra pārvietojas ar vienu noteiktu ātrumu:

Ievērojiet, ka grupā var būt arī tikai viena lokomotīve!

Uzrakstiet programmu, kas dotam sākotnējam lokomotīvju novietojumam nosaka, cik pastāvīgās grupās tās sadalīsies!

Pirmajā rindā dots naturāls skaitlis N (lokomotīvju skaits, N ≤ 1 000 000). Otrajā datnes rindā doti N dažādi naturāli skaitļi robežās no 1 līdz N - lokomotīvju numuri tādā secībā, kādā tās atrodas uz sliežu ceļa, sākot ar braukšanas virzienā pēdējo. Starp katriem diviem blakusesošiem skaitļiem ir viena tukšumzīme.

Vienīgajā rindā jāizvada viens naturāls skaitlis - grupu skaits, kādā sadalīsies lokomotīves.

6
6 2 1 4 3 5

3

6
1 2 3 4 6 5

5

 
Uzdevums izmantots Latvijas 22. informātikas olimpiādē 2009. gadā.