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。