페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#3960
다국어

Angry Cows 2초 512MB

문제

Bessie the cow가 다음 큰 히트작이 될 것이라고 생각하는 비디오 게임 "Angry Cows"를 디자인했다. 그녀는 이 게임의 개념이 완전히 독창적이라고 믿고 있다. 게임의 기본 개념은 플레이어가 소를 새총으로 발사하여 1차원 선상에 위치한 건초 더미들을 향해 쏘는 것이다. 소가 건초 더미에 착지하면 충분한 힘으로 인해 건초 더미가 폭발하며, 이로 인해 인접한 건초 더미들도 연쇄적으로 폭발할 수 있다. 목표는 한 번의 발사로 최대한 많은 건초 더미를 폭발시키는 것이다.

N개의 건초 더미가 정수 좌표 x_1, x_2, \ldots, x_N​에 위치해 있다. 소가 좌표 x에 있는 건초 더미 위에 착지하면, 이 건초 더미는 "폭발 반경"이 1인 폭발을 일으킨다. 즉, 거리 1 이내에 있는 다른 건초 더미들도 폭발에 휩싸이게 된다. 이렇게 폭발한 건초 더미들은 (모두 동시에) 다시 폭발하며, 이번에는 반경 2의 폭발을 일으켜 거리 2 이내의 추가적인 건초 더미들을 폭발시킬 수 있다. 다음 시간 단계에서는 이 건초 더미들도 (모두 동시에) 반경 3의 폭발을 일으킨다. 일반적으로, 시간 t에서 한 무리의 건초 더미가 폭발하면, 각 건초 더미는 반경 t의 폭발을 일으킨다. 이 폭발에 휩싸인 건초 더미들은 시간 t+1에서 반경 t+1의 폭발을 일으키며, 이러한 과정이 계속된다.

한 번의 소 발사로 최대한 많은 건초 더미를 폭발시킬 수 있도록, 최적의 시작 위치를 찾아 최대 폭발 개수를 구하라.


입력

첫 번째 줄에 정수 N이 주어진다. (1 \leq N \leq 100)
다음 N개의 줄에는 각각 하나의 정수 x_1, x_2, \dots, x_N​이 주어진다. (각 값의 범위는 0 \leq x_i \leq 1,000,000,000)


출력

한 번의 소 발사로 폭발할 수 있는 최대 건초 더미 개수를 출력하라.


예제1

입력
6
8
5
6
13
3
4
출력
5

이 예시에서는, 위치 5에 있는 건초 더미에 소를 발사하면, 위치 4와 6에 있는 건초 더미가 폭발하며, 각 폭발의 반경은 2가 된다. 이러한 폭발로 인해, 위치 3과 8에 있는 건초 더미가 폭발하며, 각 폭발의 반경은 3이 된다. 그러나 이 마지막 폭발들은 위치 13에 있는 건초 더미에 도달할 만큼 강하지 않다.


출처

USACO 2016 January Bronze

역링크 공식 문제집만