eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Unicycle counting

Unicycle counting

Лимит времени 10 секунд
Лимит использования памяти 256 MiB

Going to circus college is not as fun as you were led to believe. You are juggling so many classes. Trapeze class is sometimes up, sometimes down. There’s a lot of tension in your high-wire class. And you’ve seen that lion taming can be cat-astrophic.

The one pleasure you find is in riding unicycles with your fellow classmates. Many people have unicycles with different sized wheels. One day you notice that all their tires leave a small mark on the ground, once per rotation. You decide to amuse yourself and avoid your classwork by trying to determine how many unicycles have passed by on a given stretch of road. In fact, you want to know the minimum number of unique unicycles that could have left the marks you observe. You make the simplifying assumption that any unicycle riding on the road will ride completely from the beginning to the end.

The figures below illustrate the sample input. Each thick black vertical stripe represents a mark left by a tire.

Входные данные

Each line of input represents the observations on a stretch of road. A line begins with two integers 1m100 and 1n10, where m represents the length of the road and n represents the number of marks you observe on the road. These are followed by n unique integers a_1, a_2, ..., a_n, where 0a_i < m for all a_i. These n integers represent the positions where you observed a unicycle’s tire has left a mark. There will be at most 100 lines of input. Input ends at end of file.

Выходные данные

For each set of observations, print the minimum number of unicycles that could have produced the observed marks.

Пример

Входные данные #1
10 5 1 3 5 7 9
10 4 1 3 7 9
20 10 0 4 5 7 8 10 12 14 15 16
Выходные данные #1
1
2
3
Источник 2012 ACM-ICPC North American Qualification Contest