Zapałki

Limit pamięci: 32 MB

Jaś ustawił w rzędzie zapałek, jedną obok drugiej, wszystkie zwrócone główką do góry. Każda zapałka ma określoną wysokość .

Jaś może podpalić jedną zapałkę, przez co zacznie się ona spalać i zmniejszać. Podczas spalania może zdarzyć się tak, że ogień przejdzie na inne zapałki. Dzieje się to zawsze wtedy, gdy ogień znajduje się na tym samym poziomie, co główka sąsiedniej zapałki. Jaś chce wiedzieć, którą zapałkę musi podpalić na początku, aby spłonęło ich jak najwięcej.

Wejście

Pierwszy wiersz standardowego wejścia zawiera jedną liczbę całkowitą (), oznaczającą liczbę zapałek. Drugi wiersz wejścia zawiera ciąg liczb całkowitych (), gdzie oznacza wysokość -tej zapałki.

W testach wartych co najmniej punktów zachodzi dodatkowy warunek .

Wyjście

Pierwszy i jedyny wiersz standardowego wyjścia powinien zawierać jedną liczbę całkowitą, równą maksymalnej liczbie zapałek, które mogą spłonąć.

Przykład

Dla danych wejściowych:

4
2 3 1 2

poprawną odpowiedzią jest:

3

Autor zadania: Dariusz Sosnowski.