\(N\) \((1 \leq N \leq 10^5)\) коров Фермера Джона выстроены в ряд.
\(i\)-ая корова имеет метку \(a_i\) (\(1 \leq a_i \leq N\)).
Группа коров может сформировать дружескую группу, если все они имеют
одну и ту же метку и каждая корова находится в пределах \(x\) коров
от остальных коров группы, где \(x\) - целое число из интервала \([1,N]\).
Каждая корова должна быть точно в одной дружеской группе.
Для каждого \(x\) от \(1\) до \(N\), посчитайте минимальное количество
дружеских групп, которые могу быть сформированы.
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит целое число
\(N\).
Следующая строка содержит \(a_1 ... a_N\), метки каждой из коров.
ФОРМАТ ВЫВОДА (на экран / stdout):
Для каждого \(x\) от \(1\) до \(N\), выведите минимальное количество дружеских
групп для каждого \(x\) в отдельной строке.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
9
1 1 1 9 2 1 2 1 1
|
7
5
4
4
4
4
4
3
3
|