시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB21150.000%

문제

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$

서브태스크

번호배점제한
133

$x_i ≥ 0$

217

$N ≤ 100$, $-1\,000 ≤ x_i ≤ 1\,000$

328

$N ≤ 1\,000$

46

Visi $x_i$ skirtingi

516

Papildomų ribojimų nėra

예제 입력 1

5
1 2 -1 2 -2

예제 출력 1

2
  • Pradinė situacija:

  • Numetamas riešutas ties pozicija $-$2 – Vytis pajuda į kairę:

  • Riešutas virš Vyčio numetamas tiesiai ant jo:

  • Numetamas riešutas ties pozicija $2$ – Vytis pajuda į dešinę:

  • Numetamas riešutas ties pozicija $2$ – Vytis pajuda į dešinę:

  • Riešutas virš Vyčio numetamas į jo rankas:

채점 및 기타 정보

  • 예제는 채점하지 않는다.