Lazdynas

시간 제한1초메모리 제한1024 MB

요약

개암나무가 N개의 열매를 좌표에 떨어뜨리고, 다람쥐는 정확히 자기 위치에 떨어진 열매만 받으며 아니면 그 방향으로 한 칸 움직인다. 받을 수 있는 열매 수의 최댓값을 구한다.

난이도: 보통10점 중 5점
유형: 동적 계획법, 그리디
정답자: 아직 제출이 없습니다

문제

Netoliese voveriuko Vyčio namų auga draugiškas lazdynas, kuris nokina Vyčiui riešutus.

Voveriukas rinkdamas riešutus laksto ant horizontalios lazdyno šakos, virš kurios aukštai noksta riešutai ties koordinatėmis $x\_1, \dots , x\_N$ . Vytis juda taip:

Iš pradžių Vytis stovi pozicijoje $0$ .
Jei lazdynas numeta riešutą į kairę ar į dešinę nuo voveriuko, jis pajuda per vieną poziciją į tą pusę, bet riešuto nepagauna.
Jei lazdynas numeta riešutą tiesiai Vyčiui ant galvos, šis riešutą pagauna, tačiau niekur nejuda.

Lazdynas mėto riešutus taip, kad voveriukas Vytis kuo daugiau jų pagautų.

Raskite, kiek daugiausiai voveriukas Vytis gali susirinkti lazdyno riešutų.

입력

Pirmoje eilutėje duotas riešutų kiekis $N$ .

Tolimesnėse $N$ eilučių yra po vieną skaičių $x\_i$ , $1 ≤ i ≤ N$ , nurodantį $i$ -tojo riešuto koordinatę.

출력

Išveskite vieną skaičių, nurodantį, kiek daugiausiai voveriukas Vytis gali susirinkti riešutų.

제한

$1 ≤ N ≤ 100\\,000$
$-1\\,000\\,000\\, 000 ≤ x\_i ≤ 1\\, 000\\, 000\\, 000$

예제1

예제 1
입력
```
5
1 2 -1 2 -2
```
예상 출력
```
2
```