Матрёшка — деревянная игрушка в виде расписной куклы, внутрь которой можно вложить подобную ей куклу меньшего размера.
Набор матрёшек содержит одну или более матрёшку, их размеры составляют подряд идущие положительные целые числа. Таким образом, набор матрёшек описывается двумя числами: \(s\) — размером минимальной матрёшки в наборе и \(m\) — количеством матрёшек в наборе. Иными словами, набор содержит матрёшки размеров \(s, s + 1, \dots, s + m - 1\) для некоторых целых \(s\) и \(m\) (\(s,m > 0\)).
У вас было несколько наборов матрёшек. Недавно вы обнаружили, что кто-то смешал все ваши наборы в один и записал последовательность размеров кукол — целые числа \(a_1, a_2, \dots, a_n\).
Вы не помните, сколько точно у вас было наборов, поэтому хотите найти минимальное количество наборов, которое могло быть у вас изначально.
Например, если заданная последовательность имеет вид \(a=[2, 2, 3, 4, 3, 1]\). Изначально могло быть всего \(2\) набора:
- первый набор, состоящий из \(4\)-х матрешек с размерами \([1, 2, 3, 4]\);
- второй набор, состоящий из \(2\)-x матрешек с размерами \([2, 3]\).
По заданной последовательности размеров матрёшек \(a_1, a_2, \dots, a_n\) определите минимальное количество наборов матрёшек, которые могут эту последовательность составлять.
Каждый набор используется полностью, то используются все его матрёшки. Каждый элемент заданной последовательности должен соответствовать ровно одной кукле из какого-то набора.
Примечание
Первый набор входных данных разобран в условии.
Во втором наборе входных данных все матрёшки могли быть частью одного набора с минимальным размером матрёшки \(s=7\).
В третьем наборе входных данных каждая матрешка представляет собой отдельный набор.