$1$ 이상 $10^9$ 이하의 서로 다른 정수 $N$개를 임의로 정하고 가능한 모든 쌍 $N(N-1)/2$개의 차를 구한다. 이때, 서로 다른 차의 개수의 최댓값과 최솟값을 구하고 각각 실례를 구성하여라.

입력 형식

첫 번째 줄에 $N$이 주어진다. $(2 \leq N \leq 30)$

출력 형식

첫 번째 줄에 서로 다른 차의 개수의 최댓값을 출력한다.</p>

두 번째 줄에 서로 다른 차의 개수가 최댓값이 되도록 하는 $1$ 이상 $10^9$ 이하의 서로 다른 정수 $N$개를 공백으로 구분하여 출력한다.

세 번째 줄에 서로 다른 차의 개수의 최솟값을 출력한다.

네 번째 줄에 서로 다른 차의 개수가 최솟값이 되도록 하는 $1$ 이상 $10^9$ 이하의 서로 다른 정수 $N$개를 공백으로 구분하여 출력한다.

예제 입력

3

예제 출력

3
4 8 7
2
9 3 6