Santa and Sleighs

View as PDF

Submit solution

Points: 7
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

Every year, Santa has his N sleighs organized in a row with a very specific order. However, this year, a newly hired elf has messed up this order.

After promptly firing the elf, Santa asks you to reorganize the sleighs back into their original order. Although he does not know exactly what the elf did, Santa knows that the current order is a rotated version of the original order. Each rotation is defined as moving the first sleigh to the end of the row.

Because the sleighs are heavy, you want to minimize the number of adjacent swaps you must do to reorganize the sleighs. Because you don't know what order they are in, you must find this minimum for each of the N - 1 possible rotations, in order from 1 rotation up to N - 1 rotations.

Input Specification

The first line of input will contain one integer, N (1 \le N \le 10^5).

Output Specification

Output N - 1 lines, with the ith line containing the number of swaps between adjacent sleighs needed to reorganize all of the sleighs after i rotations.

Note that 64-bit integers are required to pass.

Sample Input

4

Sample Output

3
4
3

Explanation for Sample Output

After 1 rotation, the first sleigh has moved to the end. You can swap this sleigh left three times to correct the ordering.

After 2 rotations, the first two sleighs have moved to the end. You can swap them left twice each to correct the ordering.

After 3 rotations, the first three sleighs have moved to the end. You can shift the new first sleigh right three times to correct the ordering.


Comments

There are no comments at the moment.