시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 0 0 0 0.000%

문제

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ść hi.

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 ≤ 106), oznaczającą liczbę zapałek. Drugi wiersz wejścia zawiera ciąg n liczb całkowitych h1, h2, ..., hn (1 ≤ hi ≤ 109), gdzie hi 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ąć.

예제 입력 1

4
2 3 1 2

예제 출력 1

3