← 返回题目列表

Codeforces · 899/C

C. 除数

中文机器翻译题面 查看原题

Petya 有 n 个整数:1, 2, 3, ..., n。他想将这些整数分成两个非空组,使得每个组中整数之和的绝对差尽可能小。

帮助 Petya 拆分整数。 n 个整数中的每一个都应该恰好属于一组。

输入

第一行包含一个整数 n (2 ≤ n ≤ 60 000) — Petya 拥有的整数个数。

输出

在第一行中打印可能的最小绝对差。

在第二行中打印第一组的大小,后跟该组中的整数。您可以按任意顺序打印这些整数。如果有多个答案,请打印其中任何一个。

示例

输入 #1

4

输出 #1

0
2 1 4

输入 #2

2

输出 #2

1
1 1

注意

在第一个示例中,您必须将整数 1 和 4 放入第一组,将 2 和 3 放入第二组。这样每组的和是5,差的绝对值是0。

在第二个示例中,只有两个整数,并且由于两个组都应该非空,因此您必须在第一组中放入一个整数,在第二组中放入一个整数。这样每组中整数和的绝对差为1。