Андрей весь семестр не ходил на занятия по предмету «Алгоритмы и структуры данных». Когда он пришел на зачет, преподаватель решил в наказание дать ему сложное задание.
Преподаватель дал Андрею массив из n чисел a1, ..., an. После этого он попросил Андрея для каждого k от 1 до n - 1 построить на этом массиве k-ичную кучу и посчитать количество элементов, для которых нарушается свойство кучи на минимум, т.е. значение элемента меньше значения его родителя.
Андрей посмотрел в Википедии, что k-ичная куча — это корневое дерево с вершинами в элементах массива. Если пронумеровать элементы массива от 1 до n, то сыновьями элемента v являются элементы с номерами k(v - 1) + 2, ..., kv + 1 (если какие-то из этих элементов лежат за границей массива, соответствующие сыновья отсутствуют). В любой k-ичной куче у каждого элемента, кроме первого, ровно один родитель; у элемента 1 родитель отсутствует (этот элемент является корнем кучи). Обозначим за p(v) номер родителя элемента с номером v. Скажем, что для некорневного элемента v нарушается свойство кучи, если av < ap(v).
Помогите Андрею справиться с поставленным заданием!
В первой строке записано одно целое число n (2 ≤ n ≤ 2·105).
Во второй строке через пробел записано n целых чисел a1, ..., an ( - 109 ≤ ai ≤ 109).
В единственной строке выведите n - 1 число, разделяя соседние числа одним пробелом, — количество элементов, для которых нарушается свойство k-ичной кучи, при k = 1, 2, ..., n - 1.
5
1 5 4 3 2
3 2 1 0
6
2 2 2 2 2 2
0 0 0 0 0
Картинки с кучами для первого примера приведены ниже; красным выделены элементы, для которых нарушено свойство кучи.
Во втором примере все элементы равны, поэтому ни для какой пары свойство не нарушено.
| Codeforces Round 300 |
|---|
| Закончено |
