IOI '09 - Plovdiv, Bulgaria
The Plovdiv Museum of Modern Art has an exhibition of ancient Thracian
vases. There are
vases total. The first one
is a miniature of height 1 centimeter. The second one is of height 2
centimeters; the third one is 3 centimeters tall and so on until the
vase, which is
centimeters tall.
Since this is a modern art museum and the vases are ancient, the organizers
of the exhibition would like to add a modern, chaotic twist to the
presentation of the vases. They have decided to arrange the vases in a
line that satisfies the following condition: For any three vases ,
and
, such that
's height is exactly the average of the
heights of
and
, either
must be positioned to the left of
both
and
, or
must be positioned to the right of both
and
(in other words,
may not be positioned between
and
on the
line).
Write a program that, given the number of vases, determines a linear arrangement of the vases that satisfies the condition of the exhibition organizers.
Input Specification
The input contains a single line, which in turn contains a single
integer: the number of vases .
The output should contain lines, each representing the
positions
in the arrangement, in order from left to right. Line
should contain
a single integer
, the height of the vase you decided to place on
position
. All
heights should be distinct integers between
and
inclusive.
Sample Input
5
Sample Output
3
1
2
5
4
In the above arrangement, is neither between
and
, nor is it
between
and
. Also,
is not between
and
, and
is not between
and
. Thus, it satisfies the condition of the exhibition organizers.
Comments