Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
F. A Heap of Heaps

time limit per test

3 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputAndrew skipped lessons on the subject 'Algorithms and Data Structures' for the entire term. When he came to the final test, the teacher decided to give him a difficult task as a punishment.

The teacher gave Andrew an array of *n* numbers *a*_{1}, ..., *a*_{n}. After that he asked Andrew for each *k* from 1 to *n* - 1 to build a *k*-ary heap on the array and count the number of elements for which the property of the minimum-rooted heap is violated, i.e. the value of an element is less than the value of its parent.

Andrew looked up on the Wikipedia that a *k*-ary heap is a rooted tree with vertices in elements of the array. If the elements of the array are indexed from 1 to *n*, then the children of element *v* are elements with indices *k*(*v* - 1) + 2, ..., *kv* + 1 (if some of these elements lie outside the borders of the array, the corresponding children are absent). In any *k*-ary heap every element except for the first one has exactly one parent; for the element 1 the parent is absent (this element is the root of the heap). Denote *p*(*v*) as the number of the parent of the element with the number *v*. Let's say that for a non-root element *v* the property of the heap is violated if *a*_{v} < *a*_{p(v)}.

Help Andrew cope with the task!

Input

The first line contains a single integer *n* (2 ≤ *n* ≤ 2·10^{5}).

The second line contains *n* space-separated integers *a*_{1}, ..., *a*_{n} ( - 10^{9} ≤ *a*_{i} ≤ 10^{9}).

Output

in a single line print *n* - 1 integers, separate the consecutive numbers with a single space — the number of elements for which the property of the *k*-ary heap is violated, for *k* = 1, 2, ..., *n* - 1.

Examples

Input

5

1 5 4 3 2

Output

3 2 1 0

Input

6

2 2 2 2 2 2

Output

0 0 0 0 0

Note

Pictures with the heaps for the first sample are given below; elements for which the property of the heap is violated are marked with red.

In the second sample all elements are equal, so the property holds for all pairs.

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/23/2021 08:49:23 (i1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|