만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

우아한 삼각형

시간 제한2초메모리 제한1024 MB

요약
정수 n을 입력받아 n+2개 정점에 양의 정수를 배정하고, 간선 값 |v_i-v_j|가 1부터 2n+1까지 정확히 한 번씩 나오게 합니다. 불가능하면 -1을 출력합니다.
난이도

보통10점 중 7점

유형
수학, 구현
정답자
아직 제출이 없습니다

문제

다음과 같이 nn개의 정삼각형을 가로로 이어 붙인 모양의 그래프를 생각하자.

이 그래프의 정점은 n+2n+2개이고 간선은 2n+12n+1개이다. 정점은 그림과 같이 가로 위치가 증가하는 순서대로 번호가 매겨져 있다.

즉, 정점은 1부터 n+2n+2까지 번호가 붙어 있고, 번호 차이가 2 이하인 모든 정점 쌍을 잇는 간선이 있다.

각 정점에는 양의 정수가 하나씩 할당된다. 정점 ii의 값은 viv_i이다. 정점 ii와 jj를 잇는 간선의 값은 ∣vi−vj∣|v_i-v_j|이다. 1≤k≤2n+11 \le k \le 2n+1인 모든 정수 kk에 대해 값이 kk인 간선이 정확히 하나씩 있도록 정점에 값을 할당하라. 어떤 정점의 값도 101810^{18}을 넘을 수 없다.

입력

첫 줄에 양의 정수 nn이 주어진다.

출력

주어진 nn에 대해 해가 존재하면, 정점 1,2,…,n+21, 2, \ldots, n+2의 값을 공백으로 구분하여 한 줄에 출력한다. 각 값은 101810^{18} 이하의 양의 정수여야 한다. 해가 존재하지 않으면 −1-1을 출력한다.

제한

1≤n≤200 0001 \le n \le 200\,000

예제1

  1. 예제 1

    입력
    1
    
    예상 출력
    3 1 4