Фотографии на память

면접 대비

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

요약

최대 1000개의 키가 주어질 때, 크기 1, 크기 2(차이 20 이하), 크기 3(차이 10 이하)인 묶음으로 나누어 묶음 수를 최소로 만든다.

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

문제

В школе у Иэна проходит ежегодная ярмарка талантов, в которой решили принять участие $n$ существ. Рост каждого существа от $100$ до $1\\,000$ сантиметров.

Для летописи, всех участников необходимо сфотографировать. Барли вызвался на роль фотографа. Чтобы на фотографии было отчётливо видно фотографируемых, организаторы съёмки ввели правила:

На одной фотографии не должно быть больше трёх существ.
На фотографии может быть три существа, если разница в росте самого высокого и самого низкого из них не превосходит $10$ сантиметров.
На фотографии может быть два существа, если разница в их росте не превосходит $20$ сантиметров.
На фотографии может быть одно существо, независимо от его роста.

Участников довольно много, а Барли хотел бы побыстрее освободиться. Помогите ему узнать, какое минимальное число фотографий ему придётся сделать, чтобы сфотографировать всех участников.

입력

В первой строке дано одно целое число $n$ --- число участников ярмарки ( $1 \le n \le 1\\,000$ ).

Во второй строке даны $n$ чисел $a\_1, a\_2, \dots a\_n$ --- рост каждого участника ( $100 \le a\_i \le 1000$ ).

출력

Выведите одно число --- минимальное число фотографий, которое придется сделать Барли.

예제3

예제 1
입력
```
3
100 300 200
```
예상 출력
```
3
```
예제 2
입력
```
3
110 120 130
```
예상 출력
```
2
```
예제 3
입력
```
6
100 210 250 255 220 260
```
예상 출력
```
3
```