Андрей весь семестр не ходил на занятия по предмету «Алгоритмы и структуры данных». Когда он пришел на зачет, преподаватель решил в наказание дать ему сложное задание.

Преподаватель дал Андрею массив из n чисел a₁, ..., a_n. После этого он попросил Андрея для каждого k от 1 до n - 1 построить на этом массиве k-ичную кучу и посчитать количество элементов, для которых нарушается свойство кучи на минимум, т.е. значение элемента меньше значения его родителя.

Андрей посмотрел в Википедии, что k-ичная куча — это корневое дерево с вершинами в элементах массива. Если пронумеровать элементы массива от 1 до n, то сыновьями элемента v являются элементы с номерами k(v - 1) + 2, ..., kv + 1 (если какие-то из этих элементов лежат за границей массива, соответствующие сыновья отсутствуют). В любой k-ичной куче у каждого элемента, кроме первого, ровно один родитель; у элемента 1 родитель отсутствует (этот элемент является корнем кучи). Обозначим за p(v) номер родителя элемента с номером v. Скажем, что для некорневного элемента v нарушается свойство кучи, если a_v < a_p(v).

Помогите Андрею справиться с поставленным заданием!