Every year, Santa has his 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 possible rotations, in order from rotation up to rotations.
Input Specification
The first line of input will contain one integer, .
Output Specification
Output lines, with the th line containing the number of swaps between adjacent sleighs needed to reorganize all of the sleighs after rotations.
Note that 64-bit integers are required to pass.
Sample Input
4
Sample Output
3
4
3
Explanation for Sample Output
After rotation, the first sleigh has moved to the end. You can swap this sleigh left three times to correct the ordering.
After rotations, the first two sleighs have moved to the end. You can swap them left twice each to correct the ordering.
After 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