eolymp
bolt
Try our new interface for solving problems
Problems

Divide into 2 groups

Divide into 2 groups

Time limit 1 second
Memory limit 128 MiB

Divide the numbers 1, 2, ..., n into two groups so that the absolute difference between the sums of the elements in both groups be the smallest as possible.

Input data

One integer n~(2 \le n \le 10^5).

Output data

In the first line print two positive integers — the number of elements in the first and the second group.

In the second line print the elements from the first group, in the third line print the elements from the second group.

You can print the elements of each group in any order, but the elements in two groups must contain positive integers in the range [1, n].

Examples

Input example #1
4
Output example #1
2 2
1 4
2 3
Input example #2
5
Output example #2
3 2
1 2 4
3 5
Source 2022 Azerbaijan Round 1, 8-9 classes