U našem malom gradu Abenišbeu ljudi imaju različite navike i običaje, od ostatka države. Između ostalog, kod njih se domine igraju sa velikim brojem domina različitih veličina. Na nekim dominama se nalazi i do 200 brojeva poređanih u red, a na nekim i samo jedan broj. Jovica i Perica su nabavili ovakve čudne domine, ali uputstvo nije bilo u kutiji. A pošto oni nisu iz Abenišbea, ne znaju kako se igra sa dominama različitih veličina. Zato su odličili da prave nizove domina koji se ruše kad se gurne samo jedna domina. Posle nekoliko dana slaganja, složili su dugačak niz domina, sa jednakim rastojanjem između domina, ali ne znaju koliko će domina da padne ako se gurne prva. A pošto su se dosta namučili da slože, ne žele da isprobaju i izbroje domine koje su pale. Zato vi treba da im pomognete i da izračunate broj domina koje će pasti.

Ulaz:

U prvom redu ulazne datoteke domine.in nalazi se prirodan broj n (1 ≤ n ≤ 100000) koji predstavlja broj domina na stolu. U sledećih n redova se nalazi visina svake domine (1 ≤ h ≤ 200). Rastojanje između susednih domina je 1. Da bi jedna domina oborila drugu, rastojanje između njih mora biti (strogo) manje od visine te domine.

Izlaz:

U izlaznu datoteku domine.out ispisati broj domina koje će pasti ako se gurne prva domina.

Primer:

6
2 
3
1
2
1
1

5

Objašnjenje:

Prva domina ruši drugu, druga treću i četvrtu, četvrta petu, a šesta domina ostaje da stoji.

Domine obrađujemo redom, pri čemu stalno pratimo koliko domina ruše do sada obrađene domine. Domina na poziciji i visine h ruši sve domine do i+h-1 (uključujući i nju). Složenost algoritma je O(n).

Pseudokod

i = 1; 
pada = 1;     
while (pada < n) && (i ≤ pada)
	if ( h[i]+i-1 > pada )	
	   pada = h[i]+i-1;
	i = i + 1; 
if (pada>n) pada = n;
write(pada);

#include <stdio.h>

int main()
{
    freopen("domine.in","r",stdin);
    freopen("domine.out","w",stdout);
    int i,pada,n,h;
    scanf("%d",&n);
    i = 1; 
    pada = 1;     
    while ((pada<n) && (i<=pada))
    {
          scanf("%d",&h);
        if ( h+i-1 > pada )  
           pada = h+i-1;
        i++; 
    }
    if (pada>n) pada=n;
    printf("%d\n",pada);
  return 0;
}