8685번 - Zapałki 다국어

문제

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

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.

입력

Pierwszy wiersz standardowego wejścia zawiera jedną liczbę całkowitą n (1 ≤ n ≤ 10⁶), oznaczającą liczbę zapałek. Drugi wiersz wejścia zawiera ciąg n liczb całkowitych h₁, h₂, ..., h_n (1 ≤ h_i ≤ 10⁹), gdzie h_i oznacza wysokość i-tej zapałki.

출력

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

제한

힌트