У Пети есть n целых чисел: 1, 2, 3, ..., n. Он хочет разбить все свои числа на две непустые группы таким образом, чтобы модуль разности сумм чисел в каждой группе был минимально возможным.
Помогите Пети осуществить разбиение чисел. Каждое из n чисел должно быть ровно в одной группе.
Выходные данные
Выведите в первую строку минимальный модуль разности сумм чисел в каждой группе после разбиения.
Во вторую строку выведите размер первой части разбиения, а затем числа, которые должны быть в первой группе. Числа можно выводить в произвольном порядке. Если ответов несколько разрешается вывести любой из них.
Примечание
В первом примере нужно взять в первую группу числа 1 и 4, а во вторую 2 и 3. Тогда сумма в каждой группе будет равна 5, а абсолютная разность равна 0.
Во втором примере всего два числа, а так как обе группы должны быть непустыми, то одно из чисел нужно взять в первую группу, а другое — во вторую. Тогда модуль разности между суммами чисел в каждой группе будет равен 1.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
|
0
2 1 4
|
|
2
|
2
|
1
1 1
|