화난 소 (브론즈)

폭발 반경이 단계마다 1씩 커질 때 가장 많은 건초 더미를 터뜨리는 시작 위치를 구합니다.

쉬움3시뮬레이션정렬면접 대비아직 제출이 없습니다시간 제한2초메모리 제한512 MB

문제

소 베시가 새 게임 "화난 소"를 만들었다. 플레이어는 새총으로 소 한 마리를 쏘아, 수직선 위 여러 지점에 놓인 건초 더미 하나에 떨어뜨린다. 소가 떨어진 더미는 충격으로 폭발하고, 그 폭발이 근처 더미로 번져 연쇄 폭발을 일으킨다. 소 한 마리로 최대한 많은 더미를 터뜨리는 것이 목표다.

건초 더미 NN개가 수직선 위 서로 다른 정수 좌표 x1,x2,,xNx_1, x_2, \ldots, x_N에 놓여 있다. 좌표 xx에 있는 더미에 소가 떨어지면 그 더미는 폭발 반경 11로 터진다. 즉 거리가 11 이하인 다른 더미가 모두 폭발에 휩쓸린다. 휩쓸린 더미는 다음 시각에 동시에 터지고, 이때 폭발 반경은 22다. 그래서 아직 터지지 않은 더미가 거리 22 이하에 있으면 그 더미도 휩쓸린다. 그다음 시각에는 새로 휩쓸린 더미가 반경 33으로 터진다. 일반적으로 시각 tt에 터지는 더미의 폭발 반경은 tt이고, 그 폭발에 휩쓸린 더미는 시각 t+1t+1에 반경 t+1t+1로 터진다. 한 번 터진 더미는 다시 터지지 않는다.

소 한 마리를 가장 좋은 더미에 떨어뜨렸을 때 터지는 건초 더미의 최대 개수를 구하라.

입력

첫 줄에 건초 더미의 개수 NN이 주어진다. (1N1001 \le N \le 100)

다음 NN개 줄에 각 더미의 좌표 xix_i가 한 줄에 하나씩 주어진다. (0xi1090 \le x_i \le 10^9)

좌표는 모두 서로 다르고, 오름차순으로 주어진다는 보장은 없다.

출력

소 한 마리로 터뜨릴 수 있는 건초 더미의 최대 개수를 한 줄에 출력한다.

힌트

첫 번째 예제에서 좌표 55의 더미에 소를 떨어뜨리면 좌표 4466의 더미가 휩쓸려 반경 22로 터진다. 이 두 폭발이 좌표 3388의 더미를 휩쓸고, 두 더미는 반경 33으로 터진다. 반경 33으로는 좌표 1313의 더미에 닿지 않는다.