You are given a number \(n\). Your task is to determine two arrays of permutation of size \(n\) so that \( a_i \neq i\) for each \(1 \le i \le n\) and the sum of \(| a_i - i |\) for each \(1 \le i \le n\) is minimum and maximum possible.

Example

If \(n=2\), then for the minimum difference is \(2 \) and the corresponding array permutation is \(\{2,1\}\), \(|2-1|+|1-2|=2\) and the maximum difference is also \(2\) and the corresponding array permutation is \(\{2,1\}\), \(|2-1|+|1-2|=2\).

Input format

The first line contains an integer \(n \text{ }(1 \le n\le 4\times10^4)\).

Output format

In the first line, print one integer for the minimum difference.
In the second line, print permutation \(\{ a_1,a_2, \dots ,a_n\}\) corresponding to the minimum difference.
In the third line, print one integer for the maximum difference.
In the fourth line, print permutation \(\{ b_1,b_2, \dots ,b_n\}\) corresponding to the maximum difference

If there is no permutation for minimum, then print \(-1\) instead of the first and second lines.
If there is no permutation for maximum, then print \(-1\) instead of the third and fourth lines.