U zemlji Bajtoviji se, tradicionalno, svake prestupne godine održava egzibiciona reli trka. Vozaci i ekipe se okupljaju u Donjem Bitu, gde izlažu svoje automobile zainteresovanoj publici. Zatim svaki vozac dobija startni broj i trka pocinje. Vozaci krecu ka Gornjem Bitu prema startnim brojevima u razmacima od po 3 minuta. Po završetku trke, u Gornjem Bitu se održava veliko slavlje nakon koga publika i ucesnici kolektivno peru sudove. Tek nakon što su sudovi oprani, proglašava se pobednik trke. Legenda kaže da ce zavladati glad do sledeceg relija, ako se pobednik proglasi uz prljave sudove.

I tako, od pamtiveka...

Uz savremeno doba dodoše i savremena shvatanja. Ministarstvo Saobracaja, Automobilizma i Turizma, smatra da su trke suviše opasne i želi da ih zabrani uz obrazloženje da raspon od 3 minuta ostavlja veoma male manevarske mogucnosti i dovodi do neverovatno velikog broja jako rizicnih preticanja. Ako bi se interval povecao na bezbednih 7 minuta, trke bi trajale do kasno u noc kada više niko ne bi ostao da pere sudove. Potrebno je uveriti predstavnike Ministarstva da i pored raspona od 3 minuta ne dolazi do prevelikog broja preticanja.

Poznati su vam podaci vezani za poslednju održanu trku, preciznije: broj ucesnika N (1 <= N <= 100000) i redosled kojim su takmicari stizali u Gornji Bit. Od vas se ocekuje da odredite minimalan broj preticanja koji se mogao dogoditi na datoj trci.

Napomena:

Automobili takmicara su obeleženi startnim brojevima od 1 do N, i tim redom krecu sa starta. U prilog trci ide i podatak da u svakom preticanju ucestvuju samo dva vozaca. Još se nije desilo da neko od takmicara ne završi trku!

Ulaz:

U prvoj liniji standardnog ulaza nalazi se broj vozaca N. U svakoj od sledecih N linija se nalazi po jedan broj, i to u i+1-oj liniji, startni broj vozaca koji je i-ti stigao u Gornji Bit.

Izlaz:

U prvoj i jedinoj liniji standardnog izlaza potrebno je ispisati ostatak minimalnog broja preticanja pri deljenju sa 10000.

Primer:

Ulaz:
5
4
3
2
1
5

Izlaz:
6