시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB57719916933.532%

문제

투튜브의 유명 BJ인 민서는 팬들로부터 많은 사랑을 받고 있다. 팬들은 자신들의 팬심을 표현하기 위해 민서에게 많은 선물을 보내준다. 그 중 민서가 가장 좋아하는 선물은 사과이다. 이 사실을 알게 된 민서의 열혈 팬 성주는 민서에게 특별 포장 되어있는 사과세트를 보내주었다.

며칠이 지나 사과세트를 받은 민서는 포장 방식을 보고 적잖이 당황하였다. 총 2N개의 사과가 들어있었는데, 2개의 기다란 튜브에 N개씩 들어있었다. 각 튜브는 맨 앞과 끝이 뚫려 있어 총 4개의 구멍으로만 사과를 꺼낼 수 있다. 2N개의 사과는 각기 다른 크기를 가지고 있는데, 그 크기는 1부터 2N까지로 중복 없는 크기를 가지고 있다. 민서는 사과를 꺼낼 때, 구멍 쪽에 위치한 4개 이하의 사과 중 크기가 가장 작은 사과를 꺼낸다. 이 과정을 2N번 반복하여 모든 사과를 튜브에서 꺼내게 된다.

하지만 성주가 선물해준 사과는 너무 신선하여 민서가 포장을 뜯는 즉시 조금씩 부패하기 시작한다. 양의 정수 T초의 시간이 지나게 되면, 튜브 안에 들어있는 사과들은 “크기 x T”만큼의 부패도를 가지게 되고, 부패도는 누적된다.

성주도 사과가 부패한다는 사실을 당연히 알기 때문에, 민서에게 보내기 전 최대한 사과들이 부패하지 않도록 배치하려고 한다. 즉, 총 부패도가 최소가 되게 하려고 한다. 여러분이 성주의 팬심이 민서에게 전해지도록 도와주자.

입력

첫째 줄에 양의 정수 N이 주어진다. (1 ≤ N ≤ 10,000)

출력

첫째 줄에 최소의 부패도를 출력한다.

둘째 줄과 셋째 줄에 최소의 부패도를 가지는 사과의 배치를 출력한다. 만약 최소의 부패도를 가지는 사과의 배치가 여러가지 존재할 경우, 그 중 아무거나 출력한다.

예제 입력 1

2

예제 출력 1

35
1 2
3 4
  • T = 0, 누적 부패도 : 0 -> 크기 1 사과 꺼냄
  • T = 1, 누적 부패도 : 9 -> 크기 2 사과 꺼냄
  • T = 2, 누적 부패도 : 23 -> 크기 3 사과 꺼냄
  • T = 3, 누적 부패도 : 35 -> 크기 4 사과 꺼냄
  • T = 4, 누적 부패도 : 35 (최종)