레벨 디자인

시간 제한은 1000 ms, 메모리 제한은 1024 MB이다.

$0$번부터 $N+1$번까지 번호가 붙은 $N+2$개의 레벨이 있다. 각 레벨은 $0, 1, 2, \cdots, N, N+1$번 순서로 배치되어 있고, 플레이어는 $0$번 레벨에서 시작해 $N+1$번 레벨까지 순서대로 진행한다. 이전에 방문한 레벨로 돌아가거나 레벨을 건너뛰는 것은 불가능하다.

$0$번 방과 $N+1$번 방을 제외한 $N$개의 방에는 점수를 올려주는 아이템이 하나씩 놓여 있다. 플레이어가 $i$번 방에 놓인 아이템을 획득하면 $i$만큼의 점수를 얻는다. 플레이어는 각 레벨에서 아이템을 들고 갈지 자유롭게 정할 수 있으나, 연속한 두 개의 레벨에서 모두 아이템을 들고 가는 것은 불가능하다.

병윤이는 플레이어가 얻을 수 있는 최대 점수가 최소가 되도록 아이템을 재배치하려고 한다. 재배치는 다음 조건을 만족해야 한다.

• $1, 2, \cdots, N$번 방에 아이템이 정확히 하나씩 있어야 한다.
• 재배치한 후 $i$번 방에 놓인 아이템이 주는 점수를 $S_i$라 하자. $S_1, S_2, \cdots, S_N$은 $1$부터 $N$까지의 수가 정확히 한 번씩 등장하는 순열이어야 한다.

위 조건을 만족하는 아이템 배치를 하나 구하고, 그 배치에서 플레이어가 얻을 수 있는 최대 점수를 구해보자.

첫째 줄에 정수 $N$이 주어진다. ($1 \le N \le 200\ 000$)

첫째 줄에 $S_1, S_2, \cdots, S_N$을 공백으로 구분하여 출력한다.

둘째 줄에 해당 배치에서 플레이어가 얻을 수 있는 최대 점수를 출력한다.

조건을 만족하는 배치가 여러 가지라면 어떤 것을 출력해도 정답으로 인정된다.