2091. Пещеры

Как известно, много лет назад оборотни, предки Джейкоба и его семьи, жили в пещерах неподалеку от залива. Причем дабы избежать всевозможных проблем все они жили по одиночке.

Однако, это еще не все странности оборотней того времени. Каждый раз, на протяжении суток после очередного солнечного затмения, оборотни, возвращаясь с охоты, могли заходить в свои пещеры только по очень странному правилу, описанному далее.

Издревле сложилось, что оборотни всегда охотятся стаями, поэтому на момент их возвращения с охоты все пещеры пусты. Для удобства понимания правила, по которому оборотни заходят в пещеры, пронумеруем пещеры натуральными числами от `1` до `n`, начиная с самой дальней от залива пещеры.

Процесс заселения пещер состоит в следующем: сначала выбирается пещера, которую оборотни хотят заселить, или наоборот, из которой они хотят выселить оборотня. После этого, если там есть оборотень, то он выходит, а если нет, то оборотень туда заселяется.

Однако, вся сложность в том, что оборотни могут выбрать не любую пещеру, а либо пещеру с номером один, либо пещеру с номером `x+1`, где `x` – первая занятая пещера.

Определите, в каком порядке оборотни могли заселять пещеры.

В единственной строке дано одно натуральное число `n` – количество пещер и оборотней (`1\ ≤\ n\ ≤\ 20`).

В первой строке выведите число `k` – количество совершенных действий. Во второй строке выведите последовательность действий оборотней. Если пещера освобождается, то номер пещеры должен быть выведен со знаком минус. Иначе выводите просто номер заселяемой пещеры. Количество действий не должно превышать `10^6`. Если существует несколько возможных решений задачи, то разрешается вывести любое.

3

5
1 2 -1 3 1