Signal Pings

n signals start at 0. ping is a permutation of positions 1..n, and the corresponding signals are set to 1 in that order. After each ping, take a copy of the cumulative signal bitmap and sweep it from left to right, swapping every adjacent 10 in place, until a full pass makes no swap. Output the number of passes needed each time, including the final stopping pass with no swaps; this sorting does not change the cumulative bitmap used by later pings.

输入格式

The first line contains a non-negative integer n, followed by n whitespace-separated integers in 1..n, each position appearing exactly once. The original gives no numeric upper bound on n; this site covers every valid permutation that fits within the existing 32MiB per-case input budget and does not invent a small limit on n. n=0 is an empty permutation, a mathematical extension disclosed by this site.

输出格式

Output n pass counts in ping order, separated by whitespace. An already sorted bitmap still needs one pass with no swaps; for n=0, output an empty line.

样例 1

输入：

4
1 2 4 3

输出：

2 3 3 1

样例 2

输入：

4
4 3 2 1

输出：

1 1 1 1

样例 3

输入：

1
1

输出：

1

样例说明

The original example [1,2,4,3]→[2,3,3,1] is kept. The cumulative bitmaps are 1000, 1100, 1101, 1111 in turn. The final 1 proves that the stopping pass is counted; the second value 3 proves that each evaluation works on a copy of the cumulative bitmap rather than keeping the previous sorted result. These two points are disclosed as this site's explicit protocol derived from the original example. The other public examples are derived by this site.