Problem description

Jasio od lat startuje w Bajtockiej Olimpiadzie Informatycznej. Niestety, bez większych sukcesów. Po każdym konkursie analizuje swoje dotychczasowe wyniki i chce mu się płakać.

Tata Jasia, Pan Janusz–prezes, wie że morale załogi (czy tam syna) są bardzo ważne. Chce mu zatem przekazać, że nie jest tak źle. Chciałby pokazać Jasiowi, że od lat czyni on wielkie postępy, czyli że jego progres jest spory. Postanowił pokazywać spośród kolejnych wyników Jasia na kolejnych Bajtockich Olimpiadach Informatycznych ciągi ściśle rosnące. Oczywiście byłoby dobrze, żeby takich ciągów było dużo, ale z drugiej strony, byłoby też dobrze, gdyby były one możliwie długie.

Niestety, tata Jasia zna się na prowadzeniu biznesu i ewentualnie podliczaniu zysków w Excelu, ale nie potrafi programować. Pomóż mu!

Napisz program, który: wczyta wyniki Jasia osiągnięte na kolejnych Bajtockich Olimpiadach Informatycznych, dla każdej długości d wyznaczy liczbę spójnych ciągów konkursów o długości d, w których miał on wyniki ściśle rosnące i wypisze wyniki na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna N, określajaca liczbę Olimpiad, w których startował Jasio. W drugim (ostatnim) wierszu wejścia znajduje się ciąg N nieujemnych liczb całkowitych A_i, pooddzielanych pojedynczymi odstępami. Są to wyniki punktowe Jasia na kolejnych Olimpiadach.

Wyjście

Twój program powinien wypisać na wyjście ciąg co najwyżej N liczb całkowitych pooddzielanych pojedynczymi odstępami – i-ta spośród nich powinna określać liczbę spójnych kawałków ciągu wyników Jasia (o długości i) na kolejnych Olimpiadach, takich że w każdej kolejnej wynik Jasia był ściśle większy od poprzedniej. Wypisany ciąg ma się kończyć co najwyżej jednym zerem.

Ograniczenia

1 ≤ N ≤ 500 000, 0 ≤ A_i ≤ 10⁹.

Przykład

8
1 3 5 2 4 7 5 8

8 5 2 0