NC236499. Divisions
描述
Nami will get a sequence of
positive integers
soon and she wants to divide it into two subsequences.
At first, Nami has two empty sequences and
. She will consider each integer in
in order, and append it to either
or
. Nami calls sequences
she gets in the end a division of
. Note that
and
are different and subsequences can be empty, so there are
ways to divide
into
and
, which means there are
possible divisions of
.
For a division, supposing that there are integers in
and
integers in
, Nami will call it a great division if and only if the following conditions hold:
Nami defines the greatness of as the number of different great divisions of
. Now Nami gives you a magic number
, and your task is to find a sequence
with the greatness equal to
for her.
Note that the length of should not exceed
and the positive integers in
should not exceed
.
If there are several possible sequences, you can print any of them. If there is no sequence with the greatness equal to , print
.
输入描述
A single line contains an integer(
) - the magic number from Nami.
输出描述
If there is no sequence with the greatness equal to
in a single line.
Otherwise, in the first line, print the length
(
) of the sequence
.
In the second line, print
(
) - the sequence for Nami.
示例1
输入:
1
输出:
6 1 1 4 5 1 4
说明:
For the sequence , it can be shown that the only great division of
is:
示例2
输入:
2
输出:
1 1
说明:
For the sequence , it can be shown that all the divisions of
are great:
,
is empty;
is empty,
.