Državno natjecanje iz informatike 2016. / Prva podskupina (1. i 2. razred) – Drugi dan natjecanja - 3. zadatak

U polju raste niz od \(n\) stabljika suncokreta poredanih u red i označenih brojevima od \(1\) do \(n\) slijeva nadesno. Visine stabljika su označene brojevima \(h_1, . . . , h_n\).

Skakavac Flip se svako jutro razgibava skačući po stabljikama. On krene od neke odabrane stabljike te u svakom koraku skače na sve više i više stabljike. U prvom koraku Flip bira smjer u kojem će skočiti (nalijevo ili nadesno), a nakon toga u svakom koraku mora promijeniti smjer skoka (dakle ako je prvi skok nalijevo, sljedeći mora biti nadesno, pa onda opet nalijevo i tako dalje). Skokovi mogu biti proizvoljne duljine.

Za svaku stabljiku \(k\) odredite koliko najviše stabljika može Flip može posjetiti počevši od stabljike \(k\).

ULAZNI PODACI

U prvom redu nalazi se prirodni broj \(n\) \((n \leq 300 000)\) – broj stabljika. U sljedećem redu nalazi se n prirodnih brojeva \(h_1, . . . , h_n\) \((h_k ≤ 10^9)\) odvojenih razmakom – visine stabljika slijeva nadesno.

IZLAZNI PODACI

U prvi red ispišite n prirodnih brojeva \(b_1, . . . , b_n\) odvojenih jednim razmakom, gdje je bk najveći broj stabljika koje Flip može posjetiti ako krene skakati od stabljike \(k\).

BODOVANJE

• U test podacima vrijednim 40% bodova vrijedi \(n \leq 1000\)

PRIMJERI TEST PODATAKA

Ulaz

5
3 1 3 5 2

Izlaz

2 4 2 1 3

Ulaz

5
1 2 4 3 5

Izlaz

4 4 2 3 1

Ulaz

10
9 5 10 5 10 9 6 1 5 3

Izlaz

2 4 1 4 1 2 3 6 3 5